Fişierul intrare/ieşire:marcel.in, marcel.outSursăIIOT 2019-20 Runda 3
AutorAlexandru Petrescu, Andrei ConstantinescuAdăugată degeorge_stelianChichirim George george_stelian
Timp execuţie pe test3 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Marcel

De cand a inceput sesiunea fiul lui Marcel o tine din petrecere in petrecere. De aceasta data el este pus in fata a N2 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 109 + 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).

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

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 109 + 7.

Restricţii

  • 1 ≤ N ≤ 120
  • -109 ≤ X ≤ 109
  • -106 ≤ alc[i][j] ≤ 106

Exemplu

marcel.înmarcel.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

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?