Задача 746
Беспорядочный ужин

$n$ семей из четырех человек - отца, матери, сына и дочери - были приглашены в ресторан. Их всех рассадили за болльшим круглым столом с $4n$ стульями, так чтобы мужчины и женщины сидели, чередуясь.

Пусть $M(n)$ будет количеством способов размещения семей, так чтобы ни одна семья не сидела вместе. Ситается, что семья сидит вместе, только в том случае, если все ее члены сидят рядом друг с другом.

Например, $M(1)=0$, $M(2)=896$, $M(3)=890880$ и $M(10) \equiv 170717180 \pmod {1\,000\,000\,007}$

Пусть $S(n)=\displaystyle \sum_{k=2}^nM(k)$

Например, $S(10) \equiv 399291975 \pmod {1\,000\,000\,007}$

Найдите $S(2021)$. В качестве ответа приведите остаток от деления полученного результата на $1\,000\,000\,007$.

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