ZZ

The function $ZZ$ is defined as follows.

$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)$

Given four integers $a$, $b$, $c$, $d$, write a program that computes $ZZ(c, d)$.

The first line contains the number of test cases $T$. ($T \le 200$)

Each of the next $T$ lines holds one test case as four integers $a$, $b$, $c$, $d$. ($0 \le a, b \le 1000000000$, $1 \le c \le 100$, $1 \le c \times d \le 100000000$)

For each test case, print $ZZ(c, d)$ modulo $1000000009$ on its own line.