시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 21 11 11 52.381%

문제

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

  1. 아래와 같은 방법으로 크기가 n인 새로운 수열 b1, b2, ..., bN을 만든다. \[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에 대해서, ai를 bi로 바꾼다.

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

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

  1. 1 ≤ ci ≤ 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)

출력

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

예제 입력 1

3
1 1 1 1
2 2 1 1
2 3 1 1

예제 출력 1

0
2
4

힌트