Sequence and Transformation

A transformation is applied to a sequence $a_1, a_2, \ldots, a_n$ of length $n$. The transformation has two steps. First, build a new sequence $b_1, b_2, \ldots, b_n$ with the formula below.

$b_i = \left(\min_{j=1}^{n} a_j\right) - a_i + \sum_{j=1}^{n} a_j \quad (1 \le i \le n)$

Then replace the sequence $a$ with the sequence $b$, so $a_i$ takes the value $b_i$ for every $1 \le i \le n$.

For a sequence $x$ of length $n$, define $q(x) = \max_{i=1}^{n} x_i - \min_{i=1}^{n} x_i$.

The sequence $r$ is the result of applying the transformation $k$ times to some sequence, and you are given the value $q(r)$ together with $k$. Write a program that counts the sequences $c_1, c_2, \ldots, c_n$ satisfying both conditions below.

1. $1 \le c_i \le m$ for every $1 \le i \le n$.
2. $q(d) = q(r)$, where $d$ is the sequence obtained by applying the transformation $k$ times to the sequence $c$.

The first line contains the number of test cases $T$ ($1 \le T \le 10000$).

Each test case is one line with four integers $n$, $m$, $q(r)$, $k$ separated by spaces ($1 \le n, m, q(r), k \le 10^9$).

For each test case, print the answer modulo $10^9 + 7$ on its own line.