6. Odplata drepovaním

Byť vedúci na sústredení je naozaj super. Hlavne preto, že máte na starosti 32 účastníkov, ktorí vás musia poslúchať bez ohľadu na to, čo im prikážete urobiť. A tak sa noví vedúci mstia ďalšej generácii za krivdy, ktoré im boli spôsobené, keď boli ešte účastníkmi. Takto potom tento kolobeh pokračuje donekonečna

Emo si tiež živo spomína na príkoria, ktoré podstupoval na sústredeniach. Najviac nemal rád rozcvičky, lebo ho vedúci vytiahli z postele a nútili behať, skákať a drepovať. Preto sa rozhodol, že teraz donúti účastníkov drepovať on. Vymyslel si na to vskutku zaujímavý spôsob.

Najskôr všetkých účastníkov usporiadal do \(s\) zástupov. V každom z nich bolo \(r\) účastníkov. Vytvoril tak obdĺžnik veľkosti \(r \times s\). Následne si opakovane vyberal riadok alebo stĺpec tohto obdĺžnika a nútil účastníkov v danom riadku alebo stĺpci spraviť poldrep. To znamená, že ak účastník stál, tak si musel čupnúť a ak čupel, tak sa musel postaviť.

Ak napríklad ukázal na tretí stĺpec, všetci účastníci v treťom zástupe si museli čupnúť a ostatní ostali stáť. Ak potom ukázal na druhý riadok, tak všetci účastníci v druhom riadku si museli čupnúť, okrem účastníka, ktorý bol v druhom riadku a treťom stĺpci. Ten totiž už čupel a preto sa musel postaviť.

Keď to Ema prestalo baviť¹, pustil účastníkov na raňajky. Ešte pred tým si však zapamätal, že na konci čupelo presne \(k\) účastníkov. Keď potom prišiel na raňajky, sadol si vedľa Miša, ktorému vysvetlil, čo robil. Miša táto hra zaujala a chcel vedieť, koľkými spôsobmi vedel Emo docieliť stav, pri ktorom na konci čupelo \(k\) ľudí. Nevedel si s tým však poradiť, preto poprosil Ema, aby mu povedal ešte niečo viac. Emo mu preto prezradil, že keď si vyberal stĺpce a riadky, ktoré majú spraviť poldrep, riadok si vybral \(p_r\)-krát a stĺpec \(p_s\)-krát.

To už Mišovi na vyriešenie úlohy stačilo a povedal si, že vám takúto úlohu zadá, aby ste sa potrápili aj vy.

Úloha

Na začiatku mal Emo stojacich účastníkov, ktorí boli rozdelení do obdĺžnika s \(r\) riadkami a \(s\) stĺpcami. Následne Emo určoval niektoré riadky alebo stĺpce a účastníci v nich museli zmeniť svoj stav – ak stáli, museli si čupnúť, ak čupeli, museli sa postaviť.

Vypočítajte, koľkými spôsobmi mohol určiť \(p_r\) riadkov a \(p_s\) stĺpcov tak, aby na konci ostalo \(k\) čupiacich ľudí. Dve možnosti považujeme za rôzne, ak existuje riadok alebo stĺpec, ktorý bol vybratý v oboch možnostiach rôzny počet krát. Nezáleží nám teda na poradí, v akom Emo riadky a stĺpce určoval.

Keďže výsledok môže byť príliš veľký, vypíšte iba jeho zvyšok po delení číslom \(555\,555\,555\).

Formát vstupu

Vstup obsahuje päť medzerou oddelených čísel \(r\), \(s\), \(p_r\), \(p_s\) a \(k\) – počet riadkov a stĺpcov obdĺžnika, počty vybratí niektorého riadka, počty vybratí niektorého stĺpca a počet účastníkov, ktorí na konci ostali čupieť.

Pre tieto hodnoty platí, že \(1 \leq r,s \leq 1\,500\), \(0 \leq p_r,p_s \leq 1\,500\) a \(0 \leq k \leq rs\).

Naviac, v prvej sade vstupov platí, že \(1 \leq r,s,p_r,p_s \leq 10\), v druhej sade vstupov platí, že \(1 \leq r,s \leq 20\) a v tretej sade platí, že \(1 \leq r,s,p_r,p_s \leq 100\).

Formát výstupu

Vypíšte jedno číslo – počet možností, ktorými vieme určiť \(p_r\) riadkov a \(p_s\) stĺpcov tak, aby ostalo čupieť \(k\) účastníkov. Keďže toto číslo môže byť príliš veľké, vypíšte iba jeho zvyšok po delení číslom \(555\,555\,555\).

Príklad

Input:

2 2 2 2 4

Output:

4

V dvoch možnostiach vybral Emo oba riadky a jeden zo stĺpcov dvakrát. V druhých dvoch možnostiach vybral oba stĺpce a jeden z riadkov dvakrát.

Input:

2 2 0 0 1

Output:

0

Ak Emo nevybral žiaden riadok ani stĺpec, nie je možné aby niekto čupel.

Input:

8 4 12 3 8

Output:

27600