8. Pochúťka

Paulinka¹ mala jedného dňa robiť úlohu z databáz. Ako písala riešenie, uvedomila si, že jedáleň práve zatvorila. Bola nedeľa, takže aj všetky obchody boli zatvorené. Žiaľ, musela pokračovať v písaní o hlade a tak miesto databáz Paulinka premýšľala o koláčoch. A tak to aj skončilo. Jej domáca úloha obsahovala databázy všelijakých koláčov.

Keď prišla z ďalekého západu na prázdniny domov, rozhodla sa, že taká databáza koláčov je výborný nápad. Išla ho teda zrealizovať. Po chvíli plánovania prišla na to, že databáza predsalen nie je najlepší spôsob pre uloženie koláčov a namiesto databázy upečie maticu koláčov.

Matica mala \(r\) riadkov a \(s\) stĺpcov a Paulinka upiekla \(n + m\) koláčov. Najskôr prvých \(n\) položila tak, že \(i\)-ty bol v \((i \mod r)\)-tom riadku a \((i \mod s)\)-tom stĺpci.

Následne ešte na niektoré políčka matice položila zvyšných \(m\) koláčov tak, ako sa jej to páčilo. Paulinka mohla položiť aj viacero koláčov do jedného políčka.

Ako finalizovala svoju maticu, rozhodla sa, že niektoré koláče ozdobí maslovým krémom. Samozrejme, nie len tak ledabolo! Každý riadok a každý stĺpec musí obsahovať nepárny počet ozdobených koláčov. Samozrejme, žiadne rearanžovanie koláčov!

Paulinka s krémom stojí nad maticou a premýšľa, ako to urobiť. Ide to vôbec? Koľkými spôsobmi?

Úloha

Koľkými spôsobmi ide ozdobiť koláče v horeuvedenom rozložení tak, aby v každom riadku a stĺpci matice bol nepárny počet ozdobených koláčov?

Dva spôsoby sú rôzne, ak je nejaký koláč ozdobený v jednom a neozdobený v druhom. V jednom políčku môže byť aj viac koláčov.

Formát vstupu

Na prvom riadku dostanete rozmery mriežky \(r, s \leq 10^{9}\) a čísla \(r + s \leq n \leq 10^{9}\) a \(m \leq 10^{5}\) oddelené medzerou.

Na ďalšom riadku je \(m\) čísel, \(r_0\) až \(r_{r-1}\), kde \(r_i\) je riadok \(n + i\)-teho koláča.

Na treťom riadku je \(m\) čísel, \(s_0\) až \(s_{s-1}\), kde \(s_i\) je stĺpec \(n + i\)-teho koláča.

Riadky a stĺpce číslujeme od nuly.

V jednotlivých sadách vstupov platia pre \(r\), \(s\), \(n\) a \(m\) nasledovné obmedzenia:

Navyše, v tretej a siedmej sade stačí vypísať, či existuje aspoň jedno riešenie. Presnejšie, ak je odpoveď nula, tak program má vypísať nulu, a inak môže vypísať akékoľvek kladné číslo.

Formát výstupu

Vypíšte jedno číslo – počet rôznych spôsobov ozdobení koláčov. Keďže toto číslo môže byť veľmi veľké, vypíšte ho modulo \(1\,000\,000\,009\).

Príklad

Input:

2 4 6 2
1 1
3 0

Output:

8

Jeden možný spôsob ozdobenia koláčov:

Input:

6 4 50 5
0 1 2 3 4
3 3 3 3 3

Output:

743544352

Tu je možností veľa.

Input:

2 4 6 2
1 0
3 2

Output:

0