There are $N$ regions. Imagine them like a circular array. In $1$-based indexing: $1$ and $2$ are neighbors, $2$ and $3$ are neighbors, and $N$ and $1$ are also neighbors (because the array is circular). In each of the regions, there are $M$ people. So there are $N \times M$ people in total. We have to choose $K$ people from all of them. For every contiguous subarray of size $L$, there can be only one region whose people are chosen (Because the array is circular, $[1, L]$ and $[N, L-1]$ are both contiguous subarrays of size $L$). From a chosen region, we can select maximum of two people. How many ways can we choose $K$ people from them? Two ways are different if there is a person who is selected in one but not in the other. Since the answer can be huge, print it modulo $1000000007$ $(10^9 + 7)$.

Input Format
The first line contains a positive integer $T$, the number of test cases.
Each of the next $T$ lines contains four space separated integers $N, M, K$ and $L$.
$1 \leq T \leq 50$
$2 \leq N,M \leq 1000000$
$1 \leq K \leq 100000$
$2 \leq L \leq N$

Output Format
For each test case, print a single integer on a line: the number of ways modulo $1000000007$.