시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
15 초 | 64 MB | 334 | 133 | 85 | 46.196% |
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