Problem: Problem

There are numbers from 0 to N-1. I would like to select the lucky number for M + 1 days by the following methods. Randomly decide the lucky number on the first day. If the lucky number after i days is A and the lucky number after (i + 1) days is B,


B = (A + j)% N
(However, j is all integers where 0 ≤ j <N and (j / K) is an even number.)


Randomly decide from one of B required in. However, the result of a / b is an integer rounded down to the nearest whole number, and a% b is the remainder of a divided by b. K is also guaranteed to be a number that is divisible by N / K and N / K is even.

For example, when there are numbers 0,1,2,3 and K = 1.

* The lucky number next to 0 is 0 or 2
* The lucky number next to 1 is 1 or 3
* The lucky number next to 2 is 0 or 2
* The next lucky number after 3 is 1 or 3



It will be.

Then Q questions are given. The content of each question is as follows.

When the lucky number on the first day is a, how can you choose the lucky number up to b days so that the lucky number after b days becomes c? There will be a huge number of choices, so find the remainder after dividing by 1,000,000,007.

For example, if N = 4 K = 1, the first lucky number is 0 and the lucky number after 3 days is 2.

* 0-> 0-> 0-> 2
* 0-> 0-> 2-> 2
* 0-> 2-> 0-> 2
* 0-> 2-> 2-> 2



There are four ways.

Constraints

* 1 ≤ N ≤ 5000
* 1 ≤ M ≤ 5000
* 1 ≤ K ≤ 5000
* N / K is divisible
* N / K is even
* 1 ≤ Q ≤ 100000
* 0 ≤ ai <N (1 ≤ i ≤ Q)
* 0 ≤ bi ≤ M (1 ≤ i ≤ Q)
* 0 ≤ ci <N (1 ≤ i ≤ Q)

Input

The input is given in the following format.


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


Output

For each question, ask for an answer and output the remainder divided by 1,000,000,007 line by line.

Example

Input

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


Output

1
3
9
9
0
3
9
3
1
0

Solution (in CPP):

Solution:
#include <iostream>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <vector>
#include <valarray>
#include <array>
#include <queue>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <complex>
#include <random>

using namespace std;
typedef long long ll;

const ll MD = 1e9+7;
const int MN = 5050;

int n, k, f;
ll fact[MN];
ll x[MN];
int dp[MN][MN], sm[MN][MN];
void init() {
	f = n/(2*k);
	fact[0] = 1;
	for (int i = 1; i < MN; i++) {
		fact[i] = fact[i-1] * f;
		fact[i] %= MD;
	}
	dp[0][0] = 1;
	for (int j = 1; j <= 2*k; j++) {
		ll s = sm[0][j-1];
		s += dp[0][j-1];
		s %= MD;
		sm[0][j] = s;
//		sm[0][j] = sm[0][j-1] + dp[0][j-1];
	}
	for (int i = 1; i < MN; i++) {
		for (int j = 0; j < k; j++) {
			ll s = sm[i-1][j+1];
			s += sm[i-1][2*k];
			s -= sm[i-1][j+k+1];
			s %= MD;
			s = (s+MD) % MD;
			dp[i][j] = s;
//			dp[i][j] = sm[i-1][j+1] + sm[i-1][2*k] - sm[i-1][j+k+1];
		}
		for (int j = k; j < 2*k; j++) {
			ll s = sm[i-1][j+1];
			s -= sm[i-1][j-k+1];
			s %= MD;
			s = (s+MD) % MD;
			dp[i][j] = s;
//			dp[i][j] = sm[i-1][j+1] - sm[i-1][j-k+1];//dp[i-1][j]+dp[i-1][j-1]+dp[i-1][j-2]..dp[i-1][j-k+1]
		}
		for (int j = 1; j <= 2*k; j++) {
			ll s = sm[i][j-1];
			s += dp[i][j-1];
			s %= MD;
			s = (s+MD) % MD;
			sm[i][j] = s;
//			sm[i][j] = sm[i][j-1] + dp[i][j-1];
		}
	}
}

int main() {
	int m, q;
	cin >> n >> m >> k >> q;
	init();
	for (int i = 0; i < q; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		c = (c - a + n) % n;
		if (b == 0) {
			if (c == 0) {
				printf("1\n");
			} else {
				printf("0\n");
			}
			continue;
		}
		c %= 2*k;
		printf("%lld\n", fact[b-1]*dp[b][c] % MD);
	}
    return 0;
}