== include(page="template/taskheader" task_id="marcel") ==
Poveste şi cerinţă...
De cand a inceput sesiunea fiul lui Marcel o tine din petrecere in petrecere. De aceasta data el este pus in fata a $N^2^$ bauturi asezate sub forma unui tablou bidimensional cu $N$ linii si $N$ coloane. Se cunoaste continutul de alcool al bauturii de pe linia i, coloana j ca fiind $alc[i][j]$ unitati (numar intreg, posibil negativ!). Intr-o tura protagonistul are de ales intre a efectua una din $4$ actiuni:
* Bea toate bauturile de pe prima linie.
* Bea toate bauturile de pe prima coloana.
* Bea toate bauturile de pe ultima linie.
* Bea toate bauturile de pe ultima coloana.
De sigur, pentru a nu se face de ras, el nu poate efectua o actiune care rezulta in a bea mai putin de $X$ unitati in acea tura. Dupa tura bauturile respective se elimina din matrice si petrecerea continua! In orice moment protagonistul poate alege sa se opreasca (lucru chiar obligatoriu in momentul in care se termina bauturile). A doua zi Marcel a aflat din surse sigure valorile lui $N$, $X$ si $alc$ si este interesat sa afle numarul de modalitati $ANS$ in care ar fi putut decurge petrecerea, modulo $10^9^ + 7$. Doua modalitati sunt considerate diferite daca exista un moment la care fiul lui Marcel a ales sa efectueze actiuni diferite din cele $5$ posibile (consuma prima/ultima linie/coloana, sau se opreste).
h2. Date de intrare
Fişierul de intrare $marcel.in$ ...
Pe prima linie a fisierului de intrare $marcel.in$ se afla $N$ si $X$, separate prin spatiu. Urmeaza $N$ linii a cate $N$ numere intregi fiecare. Al $j$-ulea numar de pe linia $i$ reprezinta valoarea lui $alc[i][j]$.
h2. Date de ieşire
În fişierul de ieşire $marcel.out$ ...
Pe prima linie a fisierului de iesire $marcel.out$ se va afla un singur numar $ANS$, reprezentand numarul de feluri in care poate decurge petrecerea, modulo $10^9^ + 7$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 120$
* $-10^9^ ≤ X ≤ 10^9^$
* $-10^6^ ≤ alc[i][j] ≤ 10^6^$
h2. Exemplu
table(example). |_. marcel.in |_. marcel.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
table(example). |_. marcel.în |_. marcel.out |
|1 10
23
|5|
|1 23
10
|1|
|2 10
23 23
23 23
|53|
|3 4
1 4 2
3 9 -6
7 8 5
|62|
h3. Explicaţie
...
In primul caz petrecerea va avea o singura runda, in care protagonistul are de ales intre a consuma $23$ unitati (lucru posibil in $4$ moduri distincte) sau a se opri.
In al doilea caz consumul a doar $10$ unitati ar fi de ras, asa ca ramane doar varianta de a se opri.
== include(page="template/taskfooter" task_id="marcel") ==
