ZZ
\textbf{ZZ}-function, a shorter name of ZeedZaad-function is defines as followed.
\includegraphics{https://static.e-olymp.com/content/54/549c372178b271ffaf9cce931aa85135610e2639.jpg}
Given \textbf{4} integers \textbf{a}, \textbf{b}, \textbf{c} and \textbf{d}. your task is to find \textbf{ZZ(c, d)}.
\InputFile
First line of input is a number of test cases \textbf{T} ≤ \textbf{200}.
Each test case is a line containing of \textbf{4} integers \textbf{a}, \textbf{b}, \textbf{c} and \textbf{d} (\textbf{0} ≤ \textbf{a}, \textbf{b} ≤ \textbf{10^9}, \textbf{1} ≤ \textbf{c} ≤ \textbf{100}, \textbf{1} ≤ \textbf{c} x \textbf{d} ≤ \textbf{10^8}).
\OutputFile
For each test case, display \textbf{ZZ(c, d) mod 1000000009}.
Giriş verilənləri #1
5 1 1 1 1 1 1 1 4 1 1 2 3 1 1 5 5 24995 8633 1 25158567
Çıxış verilənləri #1
1 7 7 155 512203519