AT_maximum_cup_2023_b 等差数列と数え上げ

给定正整数 $N,Q$。 对于 $i=1,2,\ldots,Q$，请解决以下问题： - 从项数为 $N$，首项为 $a_i$，公差为 $d_i$ 的等差数列中选择 $k_i$ 个项，将选中项的乘积定义为该次选择的分数。请计算所有 $\binom{N}{k_i}$ 种选法得到分数之和，并将结果对 $10^9+7$ 取余后输出。

输入按照以下格式由标准输入给出。 > $N$ $Q$ > $a_1$ $d_1$ $k_1$ > $\vdots$ > $a_Q$ $d_Q$ $k_Q$

输出 $Q$ 行。第 $x$ 行输出 $i=x$ 时的答案。

### 样例解释 1 对于 $i=1$，从 $(1,2,3,4)$ 中选 $1$ 个，所有选法的分数之和为 $1,2,3,4$，总和为 $10$。 对于 $i=2$，从 $(1,2,3,4)$ 中选 $2$ 个，每种选法与分数如下，总和为 $35$。 - 选 $1,2$，分数为 $1 \times 2 = 2$。 - 选 $1,3$，分数为 $1 \times 3 = 3$。 - 选 $1,4$，分数为 $1 \times 4 = 4$。 - 选 $2,3$，分数为 $2 \times 3 = 6$。 - 选 $2,4$，分数为 $2 \times 4 = 8$。 - 选 $3,4$，分数为 $3 \times 4 = 12$。 # 数据范围 - $1 \leq N \leq 10^9$ - $1 \leq Q \leq 4000$ - $0 \leq a_i,d_i \leq 10^9$ - $1 \leq k_i \leq \min(4000,N)$ - 所有输入均为整数。 由 ChatGPT 5 翻译