CF2267G New LRT

著名城市新开通了一条 LRT（轻轨交通），这是一列沿直线路径行驶的火车。 给定两个数 $n$ 和 $m$，以及一个由 $m$ 个整数构成的数组 $c$。你现在位于位置 $0$，需要到达位置 $n$。当你处于位置 $i$ 时，可以按照以下方式乘坐列车： - 选择一个正整数 $x$，使得 $m \& x = x$，其中 $\&$ 表示按位与运算。 - 从位置 $i$ 移动到 $i+x$，并支付 $c_x$ 枚金币。 本次旅行的总费用为从位置 $0$ 到位置 $n$ 所需支付的所有金币之和。如果两次旅行的移动顺序不同或每次移动的步数不同，则这两种旅行视为不同。你的任务是，计算所有可能的旅行方案的费用之和。由于答案可能很大，请输出对 $10^9+7$ 取模的结果。

每组测试包含多组测试数据。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。接下来依次给出测试用例描述。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1\le n, m

对于每个测试用例，输出一个整数，表示所有方案的总费用对 $10^9+7$ 取模的结果。

在第一个测试用例中，到达 $n$ 有 $4$ 种方式： - $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$。 由 ChatGPT 5 翻译