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%bはaをbで割った余りとします。 また K は N / 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

の４通りです。

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 ≤ a_i < N ( 1 ≤ i ≤ Q )
• 0 ≤ b_i ≤ M ( 1 ≤ i ≤ Q )
• 0 ≤ c_i < N ( 1 ≤ i ≤ Q )

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