ZZ-функция, сокращенно от ZeedZaad-функция, определяется следующим образом.
По заданным 4 целым числам a, b, c и d найдите ZZ(c, d).
Первая строка содержит количество тестов t (t ≤ 200).
Каждый тест содержит в одной строке 4 целых числа a, b, c и d (0 ≤ a, b ≤ 10^9
, 1 ≤ c ≤ 100, 1 ≤ c * d ≤ 10^8
).
Для каждого теста вывести в отдельной строке ZZ(c, d) mod 1000000009.