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 $ に対する答えを出力せよ。

### Sample Explanation 1 $ 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 $ である。 ### Constraints - $ 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) $ - 入力はすべて整数