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)\) là \(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
bài này làm như nào vậy mọi người