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):
- dacă pătrăţelul conţine impurităţi este marcat cu
-1şi va diminua calitatea diamantului cui*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 cui*j.
Fiecare pătrăţel va fi marcat cu unul dintre cele trei numere (-1, 0, +1).
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 linie i şi coloană j marcat diferit în cele două diamante.
Cerinţă
Ajutaţi firma să poată răspunde la astfel de cereri scriind un program care pentru un anumit X găseşte numărul de diamante diferite de calitate X.
Date de intrare
Pe prima linie a fişierului de intrare diamant.in sunt scrise trei numere întregi N M X separate prin câte un spaţiu reprezentând numărul de linii, numărul de coloane ale unui diamant, şi respectiv calitatea cerută.
Date de ieşire
Pe prima linie din fişierul de ieşire diamant.out se va afla numărul de diamante diferite cu calitatea cerută, modulo 10000.
Restricţii și precizări
0 < N < 210 < M < 21
Exemplu
diamant.in
2 2 7
diamant.out
3
Explicaţie
Matricile corespunzătoare celor 3 diamante sunt:
-1 +1 +1 0 +1 +1
+1 +1 +1 +1 0 +1