Points: 100 Time limit: 1.0s Memory limit: 256M Input: stdin Output: stdout

Cho dãy số gồm \(N\) số nguyên không âm \(A_1,A_2,\ldots,A_N\). Ta có tổng AND của một dãy con gồm các phần tử \(A_{i_1},A_{i_2},\ldots,A_{i_k} (1\leq i_1<i_2<\ldots<i_k\leq N)\)\(A_{i_1}\)&\(A_{i_2}\)&\(\ldots\)&\(A_{i_k}\).

Yêu cầu: Đếm số lượng dãy con có tổng AND bằng \(0\).

Input

  • Dòng đầu chứa một số nguyên dương \(N (N \leq 10^6)\);
  • Dòng thứ hai chứa \(N\) số nguyên dương \(A_1,A_2,…,A_N (A_i\leq 10^6)\).

Output

  • In ra phần dư của số lượng dãy con có tổng AND bằng 0 trong phép chia cho \(10^9+7\)

Scoring

  • Subtask \(1\) (\(20\%\) số điểm): \(A_i \in [0,1]\).
  • Subtask \(2\) (\(30\%\) số điểm): \(N,A_i \leq 1000\).
  • Subtask \(3\) (\(50\%\) số điểm): không ràng buộc gì thêm.

Example

Test 1

Input
3 
2 3 3 
Output
0

Test 2

Input
4
0 1 2 3
Output
10

Test 3

Input
6
5 2 0 5 2 1
Output
53

Comments


  • 0
    unknown_coder    1:13 p.m. 19 jul, 2022

    bài này làm như nào vậy mọi người