==Include(page="template/taskheader" task_id="12perm")==
==Include(page="template/raw")==
12-Perm
Se defineste 12-permutarea A[1],A[2],...,A[N] ca fiind o permutare a numerelor 1,2,...,N astfel incat |A[i]-A[i+1]| pentru i=1,2,..N-1.
h2. Cerinta
Dandu-se un numar natural N calculati numarul de 12-permutari de lungime N .
h2. Date de Intrare
Prima linie a fisierului de intrare 12perm.in contine numarul natural N cu semnificatia de mai sus.
h2. Date de Iesire
In fisierul 12perm.out veti afisa X numarul de 12-permutari de lungime N modulo 1048576
h2. Restrictii si precizari
. 1 <= N <= 15.000.000
. 1048576=2^20
. Pentru 70% din teste N <= 5.500.000 .
h2. Exemplu
|12perm.in |12perm.out |
|4 |12 |
==Include(page="template/taskheader" task_id="12perm")==
Se defineste 12-permutarea $A{~1~},A{~2~},...,A{~N~}$ ca fiind o permutare a numerelor $1,2,...,N$ astfel incat $|A{~i~} - A{~i+1~}|<3$ pentru $i=1,2,...,N-1$.
h2. Cerinta
Dandu-se un numar natural $N$ calculati numarul de 12-permutari de lungime $N$.
h2. Date de Intrare
Prima linie a fisierului de intrare $12perm.in$ contine numarul natural $N$ cu semnificatia de mai sus.
h2. Date de Iesire
In fisierul $12perm.out$ veti afisa $X$ numarul de 12-permutari de lungime $N$ modulo $1048576$.
h2. Restrictii si precizari
* $1 ≤ N ≤ 15.000.000$
* $1048576 = 2^20^$
* Pentru $70%$ din teste $N ≤ 5.500.000$.
h2. Exemplu
table(example). |_. 12perm.in |_. 12perm.out |
| 4 | 12 |
h3. Explicatii
Cele $12$ 12-permutari sunt: $1 2 3 4, 1 2 4 3, 1 3 2 4, 1 3 4 2, 2 1 3 4, 2 4 3 1, 3 1 2 4, 3 4 2 1, 4 2 1 3, 4 2 3 1, 4 3 1 2, 4 3 2 1$
==Include(page="template/taskfooter" task_id="12perm")==
Explicatii
Cele 12 12-permutari sunt: 1 2 3 4 , 1 2 4 3 , 1 3 2 4 , 1 3 4 2 , 2 1 3 4 , 2 4 3 1 , 3 1 2 4 , 3 4 2 1 , 4 2 1 3 , 4 2 3 1 , 4 3 1 2 , 4 3 2 1
==Include(page="template/taskfooter" task_id="12perm")==
