== include(page="template/taskheader" task_id="chomp") ==

Poveste şi cerinţă...

 
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.

h2. Date de intrare

Fişierul de intrare $chomp.in$ ...

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.

h2. Date de ieşire