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 <bits/stdc++.h>
using namespace std;
 
 
 
int mod = 1000000007;
long long dp[5010][5010];
 
int main(){
    vector<int> mov;
    int N,K,M,Q;
    cin >> N >> M >> K >> Q;
    for(int i = 0 ; i < N ; i++){
        if( (i / K) % 2 == 0 ){
			mov.push_back(i);
            //cerr << i << endl;
        }
    }
    dp[0][0] = 1;
    for(int i = 0 ; i <= 5000 ; i++){
		int tot[5010] = {};
		
		// for(int k = 0 ; k < N ; k++){
			// printf("%3d",dp[i][k]);
			// cout << " ";
		// }
		// cout << endl;
		// for(int k = 0 ; k < N ; k++) cout << (k/K%2==0?"  ^":"   ") << " ";
		// cout << endl;
		
		for(int k = 0 ; k < mov.size() ; k++){
			tot[0] += dp[i][mov[k]%N];
			tot[0] %= mod;
		}
		
		for(int j = 1 ; j < 2*K ; j++){
			tot[j] = tot[j-1];
			int c = -1;
			for(int k = 0 ; k < N ; k += K){
				tot[j] += c*dp[i][(k+j-1)%N];
				tot[j] %= mod;
				c *= -1;
			}
		}
		
		//reverse(tot,tot+2*K);
		// for(int j = 0 ; j < 2*K ; j++) cout << tot[j] << " " ;
		// cout << endl;
		
		for(int j = 0 ; j < N ; j++){
			dp[i+1][j] += tot[(K+1+j)%(2*K)];
			dp[i+1][j] %= mod;
		}
    }
    for(int i = 0 ; i < Q ; i++){
        int a,b,c;
        cin >> a >> b >> c;
        int d = ((c-a)%N+N)%N;
        cout << (dp[b][d]%mod+mod)%mod << endl;
    }
	// for(int i = 0 ; i < 15 ; i++){
		// for(int j = 0 ; j < 15 ; j++){
			// printf("%10d ",(dp[i][j]+mod)%mod);
		// }
		// cout << endl;
	// }
     
}