Gambling Monster

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

题目描述

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, \ldots, n - 1$ . The area of the $i$ -th part is $a_i$ , which means the probability of getting integer $i$ is $\dfrac{a_i}{\sum_{j = 0}^{n - 1} a_j}$ , 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 \oplus y$ , or keep $x$ unchanged, where $\oplus$ is bitwise-xor operation.

As a gambling monster, Tukuai is greedy, so he will make $x = x \oplus y$ once $x \oplus y > x$ , or keep $x$ unchanged if $x \oplus y \leq x$ .

What is the expected number of coins that need to be paid by Tukuai to get the prize? Find the answer modulo $10^9 + 7$ . Or formally, let $M = 10^9 + 7$ . It can be shown that the answer can be expressed as an irreducible fraction $\dfrac{p}{q}$ , where $q \not\equiv 0 \pmod M$ . Find the value $p \cdot q^{-1} \bmod M$ .

输入描述:

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

The first line of each test case contains an integer $n$ ( $2 \leq n \leq 2^{16}$ and $n$ is a power of $2$ ).

The second line of each test case contains $n$ integers $a_0, a_1, a_2, \ldots, a_{n - 1} \ (1 \leq a_i \leq 10^4)$ .

It is guaranteed that the sum of $n$ over all test cases does not exceed $2^{17}$ .

输出描述:

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

示例1

输入

复制

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 $\dfrac{18}{5}$ in irreducible fraction.

题目描述

输入描述:

输出描述:

输入

输出

说明

备注: