ZZ

ZZ-funksiyası, ZeedZaad-funksiya qısaltması, aşağıdakı şəkildə təyin olunur.

Verilmiş 4 tam ədəd a, b, c və d üçün ZZ(c, d) funksiyasını hesablayın.

Giriş məlumatları

Birinci sətir testlərin sayı t (t ≤ 200) göstərir.

Hər bir test bir sətirdə 4 tam ədəd a, b, c və d (0 ≤ a, b ≤ 10^9, 1 ≤ c ≤ 100, 1 ≤ c * d ≤ 10^8) ehtiva edir.

Çıxış məlumatları

Hər bir test üçün ayrıca sətirdə ZZ(c, d) mod 1000000009 hesablayın və çıxarın.