G. New LRT
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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$$$.

Example
Input
4
3 3
2 2 1
4 5
3 1 2 4 5
5 3
9 1 5
8 3
1000000000 1000000000 1000000000
Output
15
16
271
999997081
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$$$.