Permutacions alternades P45941

Diem que una permutació $p_1, \dots, p_n$ de $\{1,\dots,n\}$ és alternada si, per a tot $i$, $2 \le i \le n-1$, es té $p_{i-1} < p_i > p_{i+1}$ o bé $p_{i-1} > p_i < p_{i+1}$. És a dir, quan un element és més gran que l’anterior, el següent és més petit, i viceversa.

Quantes permutacions de $\{1,\dots,n\}$ són alternades?

Entrada

L’entrada consisteix en diversos enters $n$ entre 1 i 1000.

Sortida

Per a cada $n$, escriviu el nombre de permutacions alternades de $\{1,\dots,n\}$. Com la resposta pot ser força gran, feu els càlculs mòdul $10^9 + 7$.