← 返回题目列表

AtCoder · maximum_cup_2023_b

B. 算术级数和计数

中文机器翻译题面 查看原题

配点 : 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 。