NumberOfPaths

nop

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

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$?
 
*Glumim.* Această problemă este mult prea cunoscută. Atât de cunoscută încât de-a lungul istoriei Comisiile au dezvoltat o precizie remarcabilă în alcătuirea testelor de acest tip. Mai exact, dându-se un număr natural $C$, Comisia poate să producă o matrice de dimensiuni rezonabile pentru care răspunsul la întrebarea de mai sus este exact $C$. Spoiler alert, asta trebuie să faceţi şi voi!

Poveste şi cerinţă...

h2. Date de intrare

Fişierul de intrare $nop.in$ va conţine numărul de teste $T$. Urmează $T$ linii, fiecare conţinând câte un număr natural $C$, numărul de drumuri necesare pentru testul respectiv.

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

h2. Date de ieşire

În fişierul de ieşire $nop.out$ se vor afla matricele soluţie pentru fiecare din cele $T$ teste. Pentru fiecare test se vor afişa numărul de linii $N$ şi numărul de coloane $M$ ale matricei. Vor urma $N$ linii de câte $M$ caractere, fără spaţii, fiecare de tip $0$ sau $1$.

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

h2. Restricţii

* Numărul de celule $(N x M)$ al fiecarei matrice pe care o afisati trebuie să fie maxim $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$

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

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

| 2
1
2
| 1 1
1
3 3
111
101
111

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

|

h3. Explicaţie
 
...
 

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