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$$.