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 <algorithm>
#include <vector>
#include <string>
#include <iostream>
namespace lc {
template <int MOD>
class ModulusInteger {
public:
	typedef ModulusInteger<MOD> self_type;
private:
	int m_value;
	static self_type unsafe_construct(int x){
		self_type y;
		y.m_value = x;
		return y;
	}
public:
	ModulusInteger()
		: m_value(0)
	{ }
	ModulusInteger(int x)
		: m_value(x % MOD)
	{
		if(m_value < 0){ m_value += MOD; }
	}
	int operator*() const { return m_value; }
	self_type &operator=(const self_type &x){
		m_value = x.m_value;
		return *this;
	}
	self_type operator+(const self_type &x) const {
		const int y = m_value + x.m_value;
		return unsafe_construct(y >= MOD ? y - MOD : y);
	}
	self_type operator-(const self_type &x) const {
		const int y = m_value - x.m_value;
		return unsafe_construct(y < 0 ? y + MOD : y);
	}
	self_type operator*(const self_type &x) const {
		return unsafe_construct(
			static_cast<long long>(m_value) * x.m_value % MOD);
	}
	self_type &operator+=(const self_type &x){ return (*this = *this + x); }
	self_type &operator-=(const self_type &x){ return (*this = *this - x); }
	self_type &operator*=(const self_type &x){ return (*this = *this * x); }
};
template <int MOD>
std::ostream& operator<<(std::ostream &os, const ModulusInteger<MOD> &x){
	os << *x;
    return os;
}
}
using namespace std;
typedef lc::ModulusInteger<1000000007> mint;
static mint dp[5001][5001];
int main(){
	ios_base::sync_with_stdio(false);
	int n, m, k, q;
	cin >> n >> m >> k >> q;
	dp[0][0] = 1;
	for(int i = 0; i < m; ++i){
		for(int j = 0; j < k; ++j){
			const mint t = dp[i][j];
			dp[i + 1][j]     += t;
			dp[i + 1][j + k] -= t;
		}
		for(int j = k; j < k + k; ++j){
			const mint t = dp[i][j];
			dp[i + 1][j]     += t;
			dp[i + 1][k + k] -= t;
			dp[i + 1][0]     += t;
			dp[i + 1][j - k] -= t;
		}
		for(int j = 0; j < k + k; ++j){
			dp[i + 1][j + 1] += dp[i + 1][j];
		}
	}
	for(int i = 0; i < q; ++i){
		int a, b, c;
		cin >> a >> b >> c;
		if(b == 0){
			cout << (a == c ? 1 : 0) << endl;
		}else{
			a %= (2 * k);
			c %= (2 * k);
			auto answer = dp[b][(c - a + 2 * k) % (2 * k)];
			if(b > 1){
				mint x = n / (k * 2), z = 1;
				--b;
				while(b > 0){
					if(b & 1){ z *= x; }
					x *= x;
					b >>= 1;
				}
				answer *= z;
			}
			cout << answer << endl;
		}
	}
	return 0;
}