Problem 628

Problem 628

Open chess positions

A position in chess is an (orientated) arrangement of chess pieces placed on a chessboard of given size. In the following, we consider all positions in which $n$ pawns are placed on a $n\times n$ board in such a way, that there is a single pawn in every row and every column.

We call such a position an open position, if a rook, starting at the (empty) lower left corner and using only moves towards the right or upwards, can reach the upper right corner without moving onto any field occupied by a pawn.

Let $f(n)$ be the number of open positions for a $n\times n$ chessboard.
For example, $f(3)=2$, illustrated by the two open positions for a $3\times 3$ chessboard below.

Open position 1

Open position 2

You are also given $f(5)=70$.

Find $f(10^8)$ modulo $1\ 008\ 691\ 207$.


国际象棋中,在给定大小的棋盘上(按照固定朝向)摆放一系列棋子,称为局面。接下来,只考虑在$n\times n$的棋盘上摆放$n$个兵,并使得每一行每一列都只有一个兵的局面。


记$f(n)$为$n \times n$棋盘上开放局面的数目。




求$f(10^8)$对$1\ 008\ 691\ 207$取余的结果。