CF2267G.New LRT

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

一座新的轻轨交通系统（LRT）在著名城市开通了。该系统是一列沿直线运行的列车。

给定两个整数 $n$ 和 $m$，以及一个由 $m$ 个整数组成的数组 $c$。你起始位置为 $0$，需要到达位置 $n$。若你当前位于位置 $i$，则可按如下方式乘坐列车：

• 选择一个正整数 $x$，使得 $m\& x = x$，其中 $\&$ 表示按位与运算；
• 从位置 $i$ 移动到位置 $i + x$，并支付 $c_x$ 枚金币。

一次行程的费用定义为从位置 $0$ 到达位置 $n$ 所需支付的金币总数。若两次行程的移动顺序不同，或某一步所选的 $x$ 值不同，则认为这两次行程不同。你的任务是计算所有可能行程的费用之和。由于答案可能很大，请将结果对 $10^9 + 7$ 取模后输出。

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

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1\le n, m\lt 2^{20}$）。

每个测试用例的第二行包含 $m$ 个整数 $c_1, c_2, \ldots, c_m$（$1\le c_i\le 10^9$）。

保证所有测试用例中 $n$ 的总和与 $m$ 的总和均不超过 $2^{20}$。

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

对于每个测试用例，输出一个数字——该问题答案对 $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$.

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

在第一个测试用例中，共有 $4$ 种方式到达位置 $n$：

• $0\rightarrow 1\rightarrow 2\rightarrow 3$。该路径的花费为 $c_1 + c_1 + c_1 = 6$。
• $0\rightarrow 1\rightarrow 3$。该路径的花费为 $c_1 + c_2 = 4$。
• $0\rightarrow 2\rightarrow 3$。该路径的花费为 $c_2 + c_1 = 4$。
• $0\rightarrow 3$。该路径的花费为 $c_3 = 1$。

因此，答案为 $6 + 4 + 4 + 1 = 15$。