== include(page="template/taskheader" task_id="magic") ==

Se dă o matrice cu $N$ linii şi $N$ coloane. Coloanele şi liniile sunt etichetate cu numere de la 1 la $2N$, folosind fiecare număr câte o singură dată (fig. $1$ – exemplu pentru $N$=$3$). Vom nota şirul etichetelor asociat liniilor matricei o{~1~},o{~2~},...,o{~n~}, iar şirul etichetelor asociat coloanelor matricei cu v{~1~},v{~2~},...,v{~n~} (fig. 4).
Trebuie să se completeze fiecare element al matricei cu una dintre cifrele $1$ sau $9$ (fig. $2$). Prin concatenarea cifrelor de pe o linie sau o coloană obţinem un număr de $N$ cifre. În total se obţin $2N$  numere. Aceste numere trebuie să fie distincte două câte două şi aranjându-le în ordinea etichetelor asociate liniilor şi coloanelor trebuie să fie în ordine crescătoare (fig. $3$). Vom concatena cele $2N$ numere în ordinea etichetelor şi obţinem un singur număr de 2$N^2$ cifre. Acest număr îl vom denumi cheie magică. Pentru exemplul din fig. $3$ obţinem cheia magică $111191199911919991$.
Se dau $x$ un număr natural, dimensiunea $N$ a matricei şi cele două şiruri de etichete o{~1~},o{~2~},...,o{~n~} respectiv v{~1~},v{~2~},...,v{~n~}. Să se tipărească numărul de chei magice distincte (dacă $x$=$1$) sau cea mai mică cheie magică ce se poate asocia matricei (dacă $x$=$2$).

Se dă o matrice cu $N$ linii şi $N$ coloane. Coloanele şi liniile sunt etichetate cu numere de la 1 la $2N$, folosind fiecare număr câte o singură dată (fig. $1$ – exemplu pentru $N$={$3$}). Vom nota şirul etichetelor asociat liniilor matricei o{~1~},o{~2~},...,o{~n~}, iar şirul etichetelor asociat coloanelor matricei cu v{~1~},v{~2~},...,v{~n~} (fig. 4).
Trebuie să se completeze fiecare element al matricei cu una dintre cifrele $1$ sau $9$ (fig. $2$). Prin concatenarea cifrelor de pe o linie sau o coloană obţinem un număr de $N$ cifre. În total se obţin $2N$  numere. Aceste numere trebuie să fie distincte două câte două şi aranjându-le în ordinea etichetelor asociate liniilor şi coloanelor trebuie să fie în ordine crescătoare (fig. $3$). Vom concatena cele $2N$ numere în ordinea etichetelor şi obţinem un singur număr de {$2$}{$N$}^{$2$} cifre. Acest număr îl vom denumi cheie magică. Pentru exemplul din fig. $3$ obţinem cheia magică $111191199911919991$.
Se dau $x$ un număr natural, dimensiunea $N$ a matricei şi cele două şiruri de etichete o{~1~},o{~2~},...,o{~n~} respectiv v{~1~},v{~2~},...,v{~n~}. Să se tipărească numărul de chei magice distincte (dacă $x$={$1$}) sau cea mai mică cheie magică ce se poate asocia matricei (dacă $x$={$2$}).

h2. Date de intrare

h2. Date de ieşire
Fişierul de ieşire magic.out va conţine o singură linie pe care va fi scris un număr natural care reprezintă:

- dacă $x$=$1$, numărul cheilor magice distincte;
- dacă $x$=$2$, cea mai mică cheie magică.

- dacă $x$={$1$}, numărul cheilor magice distincte;
- dacă $x$={$2$}, cea mai mică cheie magică.

h2. Restricţii

|9 |1 |1 |
|9 |9 |9 |
Numerele obţinute în ordinea etichetărilor:

($111$, $191$, $199$, $911$, $919$, $991$) respectiv
($119$, $191$, $199$, $911$, $919$, $999$).

({$111$}, $191$, $199$, $911$, $919$, $991$) respectiv
({$119$}, $191$, $199$, $911$, $919$, $999$).

Cele două chei  magice sunt $111191199911919991$ respectiv $119191199911919999$, dintre care prima e mai mică.