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

3 
2 3 3 

0

4
0 1 2 3

10

6
5 2 0 5 2 1

53