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