14847번 - 수열과 변환

크기가 N인 수열 a₁, a₂, ..., a_N이 있다. 이 수열에 다음과 같은 변환 연산을 적용하려고 한다.

1. 아래와 같은 방법으로 크기가 n인 새로운 수열 b₁, b₂, ..., b_N을 만든다. \[b_i = \min_{j=1}^{n}{a_j - a_i + \sum_{j=1}^{n}{a_j}} (1 \le i \le n)\]
2.  수열 a를 b로 바꾼다. 즉, 모든 1 ≤ i ≤ n에 대해서, a_i를 b_i로 바꾼다.

수열 a에 변환 연산을 총 K번 적용시켰다. 그 다음 \(q(r) = \max_{i=1}^{n}{r_i} - \min_{i=1}^{n}{r_i}\)를 계산한다. 여기서 r은 수열 a에 변환 연산을 k번 수행시킨 수열이다.

q(r)과 k를 알고 있을 때, 수열 c₁, c₂, ..., c_N의 개수를 구하는 프로그램을 작성하시오. 이때, 수열 c₁, c₂, ..., c_n은 다음과 같은 조건을 만족해야 한다.

1. 1 ≤ c_i ≤ m (1 ≤ i ≤ n)
2. q(d) = q(r) (d는 수열 c에 변환 연산을 k번 적용시킨 수열)

첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 10000)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 네 정수 n, m, q(r), k이 공백으로 구분되어져 있다. (1 ≤ n, m, q(r), k ≤ 1,000,000,000)

각각의 테스트 케이스마다 정답을 10⁹+7로 나눈 나머지를 출력한다.