5405: Gambling Monster

Tukuai, the gambling monster, is playing a gambling game with a machine consisting of a turntable and a display screen.

The turntable is divided into n parts, numbered 0,1,2,…,n−1. The area of the i-th part is ai , which means the probability of getting integer i  is , if the player turn the turntable once.

An integer x will be displayed on the screen during the game. At the beginning, x = 0. The goal of the game is to make x = n - 1 to get the prize. The player can do the following operation any times before x = n - 1 (If x = n - 1, the game ends immediately):

Pay one coin and turn the turntable once, then get an integer y. The player can choose to make x=x ⊕y , or keep x unchanged, where ⊕ is bitwise-xor operation.

As a gambling monster, Tukuai is greedy, so he will make , or keep x unchanged if x ⊕y≤x .

What is the expected number of coins that need to be paid by Tukuai to get the prize? Find the answer modulo 10e9 +7 . Or formally, let M = 10e9 + 7. It can be shown that the answer can be expressed as an irreducible fraction  p /q, where 

The first line of the input contains an integer  T (1≤T≤16), representing the number of test cases.

The first line of each test case contains an integer

The second line of each test case contains n integers  

It is guaranteed that the sum of n over all test cases does not exceed 2e17

For each test case, output the answer modulo 10e9 + 7, in a single line.

2
4
1 2 2 1
8
1 2 3 4 5 6 7 8

200000005
119223647

The answer of the first test case of the example can be expressed as 18/5 in irreducible fraction.