Marcel

marcel

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

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. 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).

Poveste şi cerinţă...

h2. Date de intrare

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]$.

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

h2. Date de ieşire

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$.

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

h2. Restricţii

* $1 ≤ N ≤ 120$
* $1 ≤ X ≤ 10^9^$
* $-10^6^ ≤ alc[i][j] ≤ 10^6^$

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

h2. Exemplu

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|

table(example). |_. marcel.in |_. marcel.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

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") ==