ZZ — Eolymp

Вхідні дані

Перший рядок містить кількість тестів $t$ ( $t \leq 200$ t \leq 200).

Кожен тест складається з одного рядка, що містить $4$ цілі числа $a$ , $b$ , $c$ і $d$ ( $0 \leq a, b \leq 1 0^{9}$ 0 \leq a, b \leq 10^9, $1 \leq c \leq 100$ 1 \leq c \leq 100, $1 \leq c \cdot d \leq 1 0^{8}$ 1 \leq c \cdot d \leq 10^8).

Вихідні дані

Для кожного тесту виведіть у окремому рядку значення $Z Z (c, d)$ ZZ(c, d) mod $1000000009$ .

Приклади

Приклад 1

Loading