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;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF 1e16
#define mod 1000000007

ll N,M,K,Q;
ll dp[5001][5001];

int main(){
  cin>>N>>M>>K>>Q;
  dp[0][0]=1;
  rep(i,M){
    ll crtdp=0;
    rep(A,N){
      ll j=(N-A)%N;
      if((j/K)%2==0)(crtdp+=dp[i][A])%=mod;
    }
    rep(B,2*K){
      for(ll b=B;b<N;b+=2*K)dp[i+1][b]=crtdp;
      rep(j,N/K){
        ll a=(j*K+(B+1))%N;
        if(j%2==0) (crtdp+=dp[i][a])%=mod;
        else (crtdp+=mod-dp[i][a])%=mod;
      }
    }
  }

  while(Q--){
    ll a,b,c;
    cin>>a>>b>>c;
    c-=a;
    if(c<0)c+=N;
    cout<<dp[b][c]<<endl;
  }
  return 0;
}