A new LRT (light rail transit) has opened in the famous city. It is a train that moves along a straight line.

You are given two numbers $n$ and $m$, and an array $c$ consisting of $m$ integers. You are at position $0$, and you need to get to position $n$. If you are at position $i$, you can ride the train as follows:

• Choose a positive integer $x$ such that $m\& x = x$, where $\&$ denotes the bitwise AND operation.
• Move from position $i$ to $i + x$, paying $c_x$ coins.

The

cost

of a trip is the total number of coins that had to be paid to get from position $0$ to position $n$. Two trips are considered different if the order of moves differs or the moves themselves differ. Your task is to determine the sum of the

costs

of all possible trips. Since the answer may be large, output it modulo $10^9 + 7$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($1\le n, m\lt 2^{20}$).

The second line of each test case contains $m$ integers $c_1, c_2, \ldots, c_m$ ($1\le c_i\le 10^9$).

It is guaranteed that the sum of $n$ and the sum of $m$ over all test cases do not exceed $2^{20}$.

Output

For each test case, output one number — the answer to the problem modulo $10^9 + 7$.

Note

In the first test case, there are $4$ ways to get to position $n$:

• $0\rightarrow 1\rightarrow 2\rightarrow 3$. The cost of this trip is $c_1 + c_1 + c_1 = 6$.
• $0\rightarrow 1\rightarrow 3$. The cost of this trip is $c_1 + c_2 = 4$.
• $0\rightarrow 2\rightarrow 3$. The cost of this trip is $c_2 + c_1 = 4$.
• $0\rightarrow 3$. The cost of this trip is $c_3 = 1$.

Thus, the answer is $6 + 4 + 4 + 1 = 15$.