0 から N-1 までの数字があります。 M+1日間のラッキーナンバーを以下の方法で選びたいと思います。 最初の日にラッキーナンバーをランダムに決めます。 i日後のラッキーナンバーを A 、(i+1)日後のラッキーナンバーを B とすると、
B = ( A + j ) % N (ただし j は 0 ≤ j < N かつ (j / K) が偶数となる全ての整数である )
で求められるBのうちのいずれかからランダムに決めます。ただし、a / b の結果は小数点以下を切り捨てた整数とし、a%bはaをbで割った余りとします。 また K は N / K が割り切れて、N / K が偶数となる数字であることが保証されます。
例えば 0,1,2,3 と数字があり、 K = 1 のとき
となります。
次にQ個の質問が与えられます。 各質問の内容は以下のとおりです。
最初の日のラッキーナンバーが a のとき b 日後のラッキーナンバーが c になるような b 日後までのラッキーナンバーの選び方は何通りでしょうか? 選び方は膨大な数になると思われるので 1,000,000,007 で割った余りを求めてください。
例えば、N=4 K=1 で、最初のラッキーナンバーが 0 で 3 日後のラッキーナンバーが 2 になるような組み合わせは
の4通りです。
入力は以下の形式で与えられる。
N M K Q a1 b1 c1 a2 b2 c2 . . . aQ bQ cQ
各質問に対し、答えを求め 1,000,000,007 で割った余りを一行ずつ順番に出力してください。
6 3 1 10 0 1 0 0 2 0 0 3 0 1 3 3 0 2 1 2 2 2 2 3 2 2 2 0 1 1 1 2 2 1
1 3 9 9 0 3 9 3 1 0