Cerința

Se consideră o matrice cu n linii şi n coloane şi elemente egale cu 0 sau 1. Să se calculeze determinantul matricei.

Date de intrare

Fișierul de intrare determinanta.in conține pe prima linie numărul n, iar pe următoarele n linii câte o pereche de numere naturale l, c, reprezentând faptul că elementul matricei de pe linia l şi coloana c are valoarea 1.

Date de ieșire

Fișierul de ieșire determinanta.out va conține pe prima linie valoarea determinantului matricei.

Restricții și precizări

• 2 ≤ n ≤ 100.000
• 1 ≤ l,c ≤ n
• Exceptând elementele din poziţiile (l,c), care sunt egale cu 1, celelalte elemente ale matricei au valoarea 0.

determinanta.in

3
1 1
2 2
3 3

determinanta.out

1

Explicație

Avem determinantul \( \begin{vmatrix}
1 & 0 & 0\\
0 & 1 & 0\\
0 & 0 & 1
\end{vmatrix}=1 \)