ZZ

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.

Приклади