== include(page="template/taskheader" task_id="chomp") ==
Jocul Chomp se joacă pe o tabletă de ciocolată de $n$ x $m$ pătrăţele, unde $n >= 1$ şi $m >= 1$. Iniţial tableta este plină. Pătrăţelele de ciocolată sunt indexate de la $(1,1)$ pentru pătrăţelul din stânga jos la $(n,m)$ pentru pătrăţelul din dreapta sus. Jucătorii fac câte o mutare pe rând. O mutare constă în alegerea unei coordonate $(i,j)$ cu $1 <= i <= n$ şi $1 <= j <= m$ la care există încă ciocolata. Jucătorul care face mutarea $(i, j)$ mănâncă toate pătrăţelele de ciocolată care se găsesc la coordonate $(y,x)$ cu $y >= i$ şi $x >= j$. Pătrăţelul de la coordonatele $(1,1)$ este otrăvit. Jucătorul care este nevoit să mănânce acest pătrăţel pierde jocul.
Date de iesire
Pentru fiecare din cele T teste, cate o linie care contine numarul de configuratii modulo 334214459.
Restrictii
1 <= n, m <= 128
Exemplu
chomp.in
1
2 2
chomp.out
6
Chomp
Jocul Chomp se joaca pe o tableta de ciocolata de n x m patratele, unde n >= 1 si m >= 1. Initial tableta este plina. Patratelele de ciocolata sunt indexate de la (1,1) pentru patratelul din stanga jos la (n,m) pentru patratelul din dreapta sus. Fiecare jucator face o cate o mutare pe rand. O mutare consta in alegerea unei coordonate (i,j) cu 1 <= i <= n si 1 <= j <= m la care exista inca ciocolata. Jucatorul care face mutarea (i, j) mananca toate patratelele de ciocolata care se gasesc la coordonate (y,x) cu y >= i si x >= j. Patratelul de la coordonate (1,1) este otravit. Jucatorul care este nevoit sa manance acest patratel pierde jocul.
Jocul Chomp este interesant din punct de vedere teoretic deoarece exista o demonstratie eleganta ca primul jucator are strategie sigura de castig. Demonstratia este bazata pe argumentului furtului de strategie. Pentru aceasta problema, nu este importanta demonstratia, deoarece se cere, dandu-se n si m, numarul de configuratii posibile in care poate ajunge jocul. Mai mult, fiindca comisia este de treaba, se cere sa se afiseze rezultatul modulo 334214459.
Jocul Chomp este interesant din punct de vedere teoretic deoarece există o demonstraţie elegantă că primul jucător are strategie sigură de câştig. Demonstraţia este bazată pe argumentului furtului de strategie. Pentru această problemă, nu este importantă demonstraţia, deoarece se cere, dându-se $n$ şi $m$, numărul de configuraţii posibile în care poate ajunge jocul fără a ţine cont de modul în care s-a ajuns la configuraţia respectivă sau de jucătorul aflat la mutare. Mai mult, fiindcă comisia este de treaba, se cere să se afişeze rezultatul modulo $334214459$.
h2. Date de intrare
Fişierul de intrare $chomp.in$, e prima linie, numarul T <= 100 de teste.
Pe fiecare din urmatoarele T linii, cate doua numere naturale n si m, reprezentand numarul de linii si numarul de coloane pentru tableta de ciocolata din testul respectiv.
Fişierul de intrare $chomp.in$ conţine, pe prima linie, numărul $T <= 100$ de teste. Pe fiecare din următoarele $T$ linii, câte două numere naturale $n$ şi $m$, reprezentând numărul de linii şi numărul de coloane pentru tableta de ciocolată din testul respectiv.
h2. Date de ieşire
În fişierul de ieşire $chomp.out$ ...
În fişierul de ieşire $chomp.out$, pentru fiecare din cele $T$ teste, câte o linie care conţine numărul de configuraţii modulo $334214459$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 <= n, m <= 128$
h2. Exemplu
table(example). |_. chomp.in |_. chomp.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 1
2 2
|6
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="chomp") ==
