---

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.

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(3)=2$，这两种开放局面如下图所示：

已知$f(5)=70$。

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

---