Fallingb

fallingb

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

Lui Gigel îi place să joace o versiune fascinantă de Falling Blocks. În această versiune de Falling Blocks, Gigel are la dispoziţie o infinitate de piese din fiecare din formele următoare:
 
!problema/fallingb?piese.jpg!
 
Scopul lui Gigel este să le aşeze într-un caroiaj de dimensiune $n x m$. E curios în câte moduri diferite poate umple caroiajul folosind tipurile de piese disponibile.

Poveste şi cerinţă...

h2. Date de intrare

Fişierul de intrare $fallingb.in$ conţine pe prima linie numărul de teste $T$. Pe fiecare din următoarele $T$ linii se găsesc câte două numere naturale $n$ şi $m$ reprezentând dimensiunea caroiajului pe care se aşează piesele.

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

h2. Date de ieşire

Pentru fiecare test din fişierul de intrare, afişaţi în fişierul de ieşire $fallingb.out$ numărul de modalităţi de umplere a caroiajului cu piesele disponibile modulo $9901$.

În fişierul de ieşire $fallingb.out$ ...

h2. Restricţii

* în toate testele folosite la evaluare, $n = 8$
* $1 ≤ m ≤ 120$
* $1 ≤ T ≤ 100$

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. fallingb.in |_. fallingb.out |

| 1
  2 2
| 11

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. Explicaţie

Sunt $11$ moduri de a umple un caroiaj de dimensiune $2$ pe $2$:
 
!problema/fallingb?moduri2x2.jpg!

...

== include(page="template/taskfooter" task_id="fallingb") ==

9535