Lucky Number

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

inputFormat

Input

The input is given in the following format.

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

outputFormat

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

样例

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

1
3
9
9
0
3
9
3
1
0

</p>