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. 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}). For each test case, output one number — the answer to the problem modulo (10^9 + 7). 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).