시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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