Lucky Number

Time Limit : 3 sec, Memory Limit : 262142 KB

Lucky Number

Problem

0 から N-1 までの数字があります。 M+1日間のラッキーナンバーを以下の方法で選びたいと思います。 最初の日にラッキーナンバーをランダムに決めます。 i日後のラッキーナンバーを A 、(i+1)日後のラッキーナンバーを B とすると、

B = ( A + j ) % N
(ただし j は 0 ≤ j < N かつ (j / K) が偶数となる全ての整数である )

で求められるBのうちのいずれかからランダムに決めます。ただし、a / b の結果は小数点以下を切り捨てた整数とし、a%babで割った余りとします。 また KN / K が割り切れて、N / K が偶数となる数字であることが保証されます。

例えば 0,1,2,3 と数字があり、 K = 1 のとき

  • 0 の次のラッキーナンバーは 0 or 2
  • 1 の次のラッキーナンバーは 1 or 3
  • 2 の次のラッキーナンバーは 0 or 2
  • 3 の次のラッキーナンバーは 1 or 3

となります。

次にQ個の質問が与えられます。 各質問の内容は以下のとおりです。

最初の日のラッキーナンバーが a のとき b 日後のラッキーナンバーが c になるような b 日後までのラッキーナンバーの選び方は何通りでしょうか? 選び方は膨大な数になると思われるので 1,000,000,007 で割った余りを求めてください。

例えば、N=4 K=1 で、最初のラッキーナンバーが 0 で 3 日後のラッキーナンバーが 2 になるような組み合わせは

  • 0 → 0 → 0 → 2
  • 0 → 0 → 2 → 2
  • 0 → 2 → 0 → 2
  • 0 → 2 → 2 → 2

の4通りです。

Input

入力は以下の形式で与えられる。

N M K Q
a1 b1 c1
a2 b2 c2
.
.
.
aQ bQ cQ

Constraints

  • 1 ≤ N ≤ 5000
  • 1 ≤ M ≤ 5000
  • 1 ≤ K ≤ 5000
  • N / K が割り切れる
  • N / K は偶数
  • 1 ≤ Q ≤ 100000
  • 0 ≤ ai < N ( 1 ≤ iQ )
  • 0 ≤ biM ( 1 ≤ iQ )
  • 0 ≤ ci < N ( 1 ≤ iQ )

Output

各質問に対し、答えを求め 1,000,000,007 で割った余りを一行ずつ順番に出力してください。

Sample Input1

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

Sample Output1

1
3
9
9
0
3
9
3
1
0

Source: Aizu Competitive Programming Camp 2015 Day2 , Japan, 2015-09-22