시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
15 초 64 MB 111 14 13 28.261%

문제

ZZ 함수의 정의는 다음과 같다.

\(ZZ(0,1) = a\)

\(ZZ(0,2) = b\)

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

\(ZZ(i,k) = \sum _{j=1} ^{k} {ZZ(i-1,j)} ; i \ge 1, k \ge 1\)

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

입력

첫째 줄에 테스트 케이스의 개수 T ≤ 200 가 주어진다. 

각 테스트 케이스는 네 정수 a, b, c, d로 이루어져 있다. (0 ≤ a, b ≤ 1 000 000 000, 1 ≤ c ≤ 100, 1 ≤ c x d ≤ 100 000 000)

출력

각 테스트 케이스마다 ZZ(c, d) mod 1 000 000 009를 출력한다. 

예제 입력

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

예제 출력

1
7
7
155
512203519

힌트