Задача 628
Открытые шахматные позиции

Шахматная позиция - это направленное расположение шахматных фигур на шахматной доске определенного размера. В этой задаче рассмотрим все позиции, в которых $n$ пешек расставлены на доске $n \times n$ таким образом, что в каждом ряду и столбце доски находится всего одна пешка.

Назовем такую позицию открытой, если ладья, помещенная в пустом нижнем левом углу доски, может попасть в правый верхний угол доски, используя ходы только в направлениях вверх и направо.

Пусть $f(n)$ будет количеством открытых позиций на шахматной доске $n \times n$.
Например, $f(3)=2$, что показано двумя открытыми позициями на доске $3 \times 3$ ниже.

Open position 1 Open position 2

Вам также дано, что $f(5)=70$.

Найдите остаток от деления $f(10^8)$ на $1\,008\,691\,207$.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net