ZZ-функция, сокращенно от ZeedZaad-функция, определяется следующим образом.

По заданным 4 целым числам a, b, c и d найдите ZZ(c, d).

Входные данные

Первая строка содержит количество тестов t (t ≤ 200).

Каждый тест содержит в одной строке 4 целых числа a, b, c и d (0 ≤ a, b ≤ 109, 1 ≤ c ≤ 100, 1 ≤ c * d ≤ 108).

Выходные данные

Для каждого теста вывести в отдельной строке ZZ(c, d) mod 1000000009.