Aproapeperm

Cerință

Dată fiind o valoare $n$, să se determine câte permutări de lungime $n$ există astfel încât orice valoare $i$ se află pe una dintre pozițiile $i-1$, $i$, $i+1$. În plus, nu sunt permise $3$ puncte fixe consecutive (dacă pe poziția $i$ se află chiar valoarea $i$, spunem că acolo este un punct fix).

Date de intrare

Pe prima linie a fișierului de intrare aproapeperm.in se află valoarea $n$.

Date de ieșire

Fișierul de ieșire aproapeperm.out va conține un singur număr întreg, reprezentând valoarea cerută modulo $10^9+7$.

Restricții și precizări

• Pentru teste in valoare de 19 de puncte 1$\leq n \leq 8$;
• Pentru alte teste in valoare de 22 de puncte 1$\leq n \leq 40$;
• Pentru alte teste in valoare de 59 de puncte 1$\leq n \leq 100 \ 000$;

Exemplul 1

aproapeperm.in

6

aproapeperm.out

8

Explicație

Permutările numărate sunt:

1 2 4 3 5 6
1 2 4 3 6 5
1 3 2 4 6 5
1 3 2 5 4 6
2 1 3 4 6 5
2 1 3 5 4 6
2 1 4 3 5 6
2 1 4 3 6 5