Fişierul intrare/ieşire:	matperm.in, matperm.out	Sursă	Selectie echipe ACM ICPC, UPB 2009
Autor	Andrei Homescu	Adăugată de	Mugurel-Ionut Andreica •mugurelionut
Timp execuţie pe test	0.4 sec	Limită de memorie	12288 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Matperm

Fie o matrice A de dimensiune NxN cu numere naturale. Permanentul matricei este suma tuturor produselor A[1, p[ 1 ]] x A[2, p[ 2 ]] x ... x A[N, p[ N ]] pentru toate permutarile posibile p ale elementelor {1, 2, ..., N}. De exemplu, permanentul unei matrici 2×2 este: P=A[1,1]xA[2,2] + A[1,2]xA[2,1].

Fiind data o matrice A, sa se calculeze permanentul acesteia modulo 9901.

Date de intrare

Pe prima linie a fisierului de intrare matperm.in se afla numarul intreg N. In continuare urmeaza N linii cu cate N valori fiecare, reprezentand elementele matricei. Toate numerele de pe aceeasi linie sunt separate prin cate un spatiu.

Date de ieşire

Fisierul de iesire matperm.out va contine un singur numar, permanentul modulo 9901.

Restricţii

• 2 ≤ N ≤ 20
• 0 ≤ A[i,j] ≤ 10.000
• Pentru 30% dintre teste, N ≤ 10
• Pentru 70% dintre teste, N ≤ 16

Exemplu

Cum se trimit solutii?