配点 : 100 点
問題文
正整数 N,Q 。 对于
i=1,2,\ldots,Q 的以下问题。 从
- 項数 N、初項 a_i 、公差 d_i 的算术级数 当选择 k_i 项时,分数是所选项的乘积。\binom{N}{k_i} 街道选择的分数总和 除以 (10^9+7) 求余数。
制約
- 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)
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N Q a_1 d_1 k_1 \vdots a_Q d_Q k_Q
出力
Q 行。 x 在线 i=x 的答案。
入力例 1
4 3 1 1 1 1 1 2 3 5 3
出力例 1
10 35 3318
i=1 中
由于 (1,2,3,4) 减去 1 计算每种选择方法的分数总和。如何选择
当选择 1,2,3,4 时, 4 每个分数是 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 。