ZZ

함수 $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$로 나눈 나머지를 한 줄에 하나씩 출력한다.