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

题目描述

Country A has N cities, labeled from 1 to N.

At the beginning, the government needs to build roads between these cities. The king of Country A loves binary numbers, so he assigns a number to each city --- the number for the i-th city is A_i.

For any two cities i and j (where i < j), the king builds F(A_i \& A_j) directed roads from city i to city j. (The meaning of the symbols is explained at the end of the problem.)

Now, the king wants to know: How many ways are there going from city 1 to city N? The answer should be printed modulo 10^9 + 7.

The function F(x) counts how many 1's are in the binary (base-2) form of x. For example, F(5) = 2 (since 5 in binary is 101, which has two 1's). \& denotes the bitwise AND, for example:

\begin{aligned}<br />& \ \ 10101010 \\<br />\& \ \ & \ \ 11110000 \\<br />& -------- \\<br />& \ \ 10100000<br />\end{aligned}

which denotes 170 \& 240 = 160.

输入描述:

The first line contains an integer T (1 \le T \le 5), denoting the number of test cases.

For each test case, the first line contains an integer N (2 \le N \le 2 \times 10^5), denoting the number of cities.

The second line contains N integers A_1, A_2, \ldots, A_N (1 \le A_i < 2^{30}).

输出描述:

For each test case, output the number of different paths from city 1 to city N, modulo 10^9 + 7.
示例1

输入

复制 
3
3
7 4 5
5
3 3 3 3 3
5
290109 290105 278130 123019 100290

输出

复制 
3
54
990

备注:

There are three paths of the first test case: 1 \to 2 \to 3, 1 \to 3, 1 \to 3. Note that travel through different roads of the same two cities denotes different paths.