==Include(page="template/raw")==

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*.

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*.

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.

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*.

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*

* $1 ≤ N ≤ 15.000.000$

* *1048576=2^20^*

* $1048576=2^20^$

* Pentru *70%* din teste *N ≤ 5.500.000*.

* Pentru $70%$ din teste $N ≤ 5.500.000$.

h2. Exemplu

h2. 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*

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")==