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 is a number of test cases t (t ≤ 200).
Each test case is a line containing 4 integers a, b, c and d (0 ≤ a, b ≤ 10^9
, 1 ≤ c ≤ 100, 1 ≤ c * d ≤ 10^8
).
For each test case print ZZ(c, d) mod 1000000009.