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

Poveste şi cerinţă...

Fie $A$ o matrice binară cu $N$ linii şi $M$ coloane. Se numeşte drum "dreapta-jos" orice succesiune de celule $(x0, y0), (x1, y1) ... (x(k - 1), y(k - 1)) cu proprietatea că oricare ar fi $1 ≤ i ≤ k - 1$, $x(i) = x(i - 1) + 1 şi y(i) == y(i - 1) sau x(i) == x(i - 1) si y(i) = y(i - 1) + 1$. Câte drumuri "dreapta-jos" există care încep în colţul din stânga sus, se termină în colţul dreapta jos şi conţin doar celule de tip $1$?

h2. Date de intrare

h2. Restricţii

* aria maxima a unei matrici pe care o afisati este $1600$

* Aria maxima a unei matrici pe care o afisati este $1600$

* $1 ≤ T ≤ 500$
* $1 ≤ C{~i~} ≤ 66.666.666$

* pentru teste in valoare de $10$ puncte, $C{~i~} ≤ 800$
* pentru teste in valoare de $30$ de puncte, $C{~i~} ≤ 50.000$
* pentru teste in valoare de $50$ de puncte, $C{~i~} ≤ 1.000.000$

* Pentru teste in valoare de $10$ puncte, $C{~i~} ≤ 800$
* Pentru teste in valoare de $30$ de puncte, $C{~i~} ≤ 50.000$
* Pentru teste in valoare de $50$ de puncte, $C{~i~} ≤ 1.000.000$

h2. Exemplu