수열과 변환

크기가 $n$인 수열 $a_1, a_2, \ldots, a_n$에 변환 연산을 적용한다. 변환 연산은 두 단계로 이루어진다. 먼저 새 수열 $b_1, b_2, \ldots, b_n$을 다음 식으로 만든다.

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

그다음 수열 $a$를 수열 $b$로 바꾼다. 즉 모든 $1 \le i \le n$에 대해 $a_i$의 값을 $b_i$로 바꾼다.

길이가 $n$인 수열 $x$에 대해 $q(x) = \max_{i=1}^{n} x_i - \min_{i=1}^{n} x_i$로 정의한다.

수열 $r$은 어떤 수열에 변환 연산을 $k$번 적용한 결과이고, $q(r)$의 값과 $k$를 알고 있다. 이때 다음 두 조건을 모두 만족하는 수열 $c_1, c_2, \ldots, c_n$의 개수를 구하는 프로그램을 작성하시오.

1. 모든 $1 \le i \le n$에 대해 $1 \le c_i \le m$이다.
2. $q(d) = q(r)$이다. 여기서 $d$는 수열 $c$에 변환 연산을 $k$번 적용한 수열이다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다 ($1 \le T \le 10000$).

각 테스트 케이스는 한 줄로 이루어지며, 네 정수 $n$, $m$, $q(r)$, $k$가 공백으로 구분되어 주어진다 ($1 \le n, m, q(r), k \le 10^9$).

각 테스트 케이스마다 정답을 $10^9 + 7$로 나눈 나머지를 한 줄에 출력한다.