A - A special permutation
Time limit: 2 s
Memory limit: 256 MiB
Languages: C, C++, Java, Python, ...
Fito is playing with permutations once again. Let $A =(A_1,\, A_2,\, \cdots,\, A_N)$ be a permutation of $(1, 2,..., N)$ with $N \geq 2$. He says that $A$ is special if and only if it satisfies that the length of the longest increasing block is at most $2$ and the elements $1$ and $N$ are inverted, that means the position of $N$ is smaller than the position of $1$. A block, in this case, refers to any sequence of elements at consecutive positions in $A$.
Your task is to help Fito counting the number of special permutations modulo $10^9+7$.