== include(page="template/taskheader" task_id="diamant") ==
O firmă produce un tip nou de diamante de formă dreptunghiulară şi de calităţi diferite. Pentru a calcula calitatea unui diamant firma împarte diamantul în $N*M$ pătrăţele formând o matrice cu $N$ linii numerotate de la $1$ la $N$ şi $M$ coloane numerotate de la $1$ la $M$. Pătrăţelul de pe linia $i$ şi coloana $j$ poate influenţa calitatea diamantului în felul următor ($1≤i≤N, 1≤j≤M$)
O firma produce un tip nou de diamante de forma dreptunghiulara si de calitati diferite. Pentru a calcula calitatea unui diamant firma imparte diamantul in $N*M$ patratele formand o matrice cu $N$ linii numerotate de la $1$ la $N$ si $M$ coloane numerotate de la $1$ la $M$. Patratelul de pe linia $i$ si coloana $j$ poate influenta calitatea diamantului in felul urmator $(1≤i≤N 1≤j≤M)$
* dacă pătrăţelul conţine impurităţi este marcat cu $-1$ şi va diminua calitatea diamantului cu $i*j$
* dacă pătrăţelul este simplu este marcat cu $0$ şi nu schimbă calitatea diamantului
* dacă pătrăţelul conţine aur este marcat cu $+1$ şi va mări calitatea diamantului cu $i*j$
* daca patratelul contine impuritati este marcat cu $-1$ si va diminua calitatea diamantului cu $i*j$
* daca patratelul este simplu este marcat cu $0$ si nu schimba calitatea diamantului
* daca patratelul contine aur este marcat cu $+1$ si va mari calitatea diamantului cu $i*j$
Fiecare pătrăţel va fi marcat cu unul dintre cele trei numere $(-1, 0, +1)$.
Fiecare patratel va fi marcat cu unul dintre cele trei numere $(-1, 0, +1)$.
Un client bogat vrea sa cumpere cat mai multe diamante diferite, de aceeasi calitate $X$. Doua diamante sunt diferite daca exista cel putin un patratel de pe o linie $i$ si coloana $j$ marcat diferit in cele doua diamante.
Un client bogat vrea să cumpere cât mai multe diamante diferite, de aceeaşi calitate $X$. Două diamante sunt diferite dacă există cel puţin un pătrăţel de pe o line $i$ şi coloană $j$ marcat diferit în cele două diamante.
h2. Cerinta
Ajutati firma sa poata raspunde la astfel de cereri scriind un program care pentru un anumit $X$ gaseste numarul de diamante diferite de calitate $X$.
h2. Date de intrare
...
Pe prima linie a fisierului de intrare $diamant.in$ sunt scrise trei numere intregi $N$ $M$ $X$ separate prin cate un spatiu reprezentand numarul de linii, numarul de coloane ale unui diamant, si respectiv calitatea ceruta.
h2. Date de iesire
...
Pe prima linie din fisierul de iesire $diamant.out$ se va afla numarul de diamante diferite cu calitatea ceruta, modulo $10000$.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 20$
* $1 ≤ M ≤ 20$
* $-2^31^+1 ≤ X ≤ 2^31^-1$
h2. Exemplu
table(example). |_. diamant.in |_. diamant.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 2 2 7
| 3
|
h3. Explicatie
...
Matricile corespunatoare celor 3 diamante sunt:
$-1 +1 +1 0 +1 +1$
$+1 +1 +1 +1 0 +1$
== include(page="template/taskfooter" task_id="diamant") ==
