==Include(page="template/taskheader" task_id="12perm")==

==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~}|<3$ 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*
 
* *1048576=2^20^*
 
* Pentru *70%* din teste *N <= 5.500.000*.

* $1 ≤ N ≤ 15.000.000$
* $1048576 = 2^20^$
* Pentru $70%$ din teste $N ≤ 5.500.000$.

h2. Exemplu

|_. 12perm.in |_. 12perm.out |

table(example). |_. 12perm.in |_. 12perm.out |

| 4 | 12 |

h2. Explicatii

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*

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

731