ZZ

시간 제한15초메모리 제한64 MB

요약

a와 b에서 시작하는 피보나치 형태 수열에 누적합을 c번 적용한 뒤 d번째 값을 1000000009로 나눈 나머지를 구합니다.

난이도: 어려움10점 중 8점
유형: 조합론, 정수론, 동적 계획법
정답자: 아직 제출이 없습니다

문제

함수 $ZZ$ 는 다음과 같이 정의한다.

$ZZ(0, 1) = a$

$ZZ(0, 2) = b$

$ZZ(0, k) = ZZ(0, k-1) + ZZ(0, k-2) \quad (k > 2)$

$ZZ(i, k) = \sum_{j=1}^{k} ZZ(i-1, j) \quad (i \ge 1,\ k \ge 1)$

네 정수 $a$ , $b$ , $c$ , $d$ 가 주어졌을 때 $ZZ(c, d)$ 를 구하는 프로그램을 작성하시오.

입력

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

다음 $T$ 개 줄에 테스트 케이스가 한 줄에 하나씩, 네 정수 $a$ , $b$ , $c$ , $d$ 로 주어진다. ( $0 \le a, b \le 1000000000$ , $1 \le c \le 100$ , $1 \le c \times d \le 100000000$ )

출력

각 테스트 케이스마다 $ZZ(c, d)$ 를 $1000000009$ 로 나눈 나머지를 한 줄에 하나씩 출력한다.

예제1

예제 1

입력

5
1 1 1 1
1 1 1 4
1 1 2 3
1 1 5 5
24995 8633 1 25158567

예상 출력