ZZ-function, a shorter name of ZeedZaad-function is defines as followed.
Given 4 integers a, b, c and d. your task is to find ZZ(c, d).
First line of input is a number of test cases T ≤ 200.
Each test case is a line containing of 4 integers a, b, c and d (0 ≤ a, b ≤ 10^9, 1 ≤ c ≤ 100, 1 ≤ c x d ≤ 10^8).
For each test case, display ZZ(c, d) mod 1000000009.