No.93 Pegasus
krotonProblem Statement
Naoki has a shogi board of \(N \times N\) squares and \(N\) mysterious pieces called "Pegasus". A "Pegasus" is a piece that combines the moves of a rook and a knight (keima).
Figure: The moves of a "Pegasus". It can move any number of squares vertically and horizontally.
One day, while arranging the pieces at random, he discovered that there exist "arrangements of \(N\) Pegasi such that none of them can capture another".
Write a program that computes the number of piece arrangements satisfying this condition, modulo \(10^9 + 7\).
Here, the pieces are indistinguishable, and all of them are assumed to face upward.
Figure: An example for \(4\times 4\).
Input
\(N\)
\(N(1\leq N\leq 1000)\) is given.
Output
Output the number of piece arrangements satisfying the condition, modulo \(10^9 + 7\).
Sample
Sample 1
Input
2
Output
2
Sample 2
Input
4
Output
8
Sample 3
Input
8
Output
7208
Sample 4
Input
10
Output
605864
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。