問題文

正整数 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)
• 入力はすべて整数

入力例 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 である。