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 <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


struct Info{
	Info(int arg_start,int arg_end){
		start = arg_start;
		end = arg_end;
	}
	int start,end;
};

ll dp[5001][5001],work[16000];


int main(){

	int N,M,K,Q;

	scanf("%d %d %d %d",&N,&M,&K,&Q);

	int LIMIT = 0;
	while(LIMIT < N)LIMIT += 2*K;

	vector<Info> V;

	for(int day = 0; day <= M; day++){
		for(int num = 0; num <= N-1; num++)dp[day][num] = 0;
	}

	dp[0][0] = 1;

	for(int day = 0; day <= M-1; day++){

		for(int i = 0; i < 2*N; i++)work[i] = 0;

		for(int num = 0; num <= N-1; num++){

			if(dp[day][num] == 0)continue;

			work[num] += dp[day][num];
			work[num+K] -= dp[day][num];
			work[num+LIMIT] -= dp[day][num];
			work[num+LIMIT+K] += dp[day][num];
		}

		for(int i = 1; i < 2*N; i++){
			work[i] += work[i-1];
		}

		for(int i = 0; i < 2*N; i++){
			if(i+2*K < 2*N){
				work[i+2*K] += work[i];
			}else{
				break;
			}
		}

		for(int i = 0; i < 2*N; i++){
			dp[day+1][i%N] += work[i]%MOD;
		}
	}

	int a,b,c;

	for(int loop = 0; loop < Q; loop++){
		scanf("%d %d %d",&a,&b,&c);

		c = (c-a+N)%N;

		printf("%lld\n",dp[b][c]%MOD);
	}

	return 0;
}