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 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.
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 line 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
0 < N < 21
0 < M < 21
-231 < X < 231
Exemple
diamant.in
diamant.out
Explicaţii
2 2 7
3
Matricile corespunzătoare celor 3 diamante sunt:
-1 +1 +1 0 +1 +1
+1 +1 +1 +1 0 +1