\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}.