XOR

题号：NC51087
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

Bobo has a set A of n integers $a_1, a_2, \dots, a_n$ .
He wants to know the sum of sizes for all subsets of A whose xor sum is zero modulo $(10^9+7)$ .
Formally, find $\left(\sum_{S \subseteq A, \oplus_{x \in S} x = 0} |S|\right) \bmod (10^9+7)$ . Note that $\oplus$ denotes the exclusive-or (XOR).

输入描述:

The input consists of several test cases and is terminated by end-of-file.

The first line of each test case contains an integer n.
The second line contains n integers .

* 
* 
* The number of test cases does not exceed 100.
* The sum of n does not exceed .

输出描述:

For each test case, print an integer which denotes the result.

示例1

输入

复制

1
0
3
1 2 3
2
1000000000000000000 1000000000000000000

输出

复制

1
3
2