Дастархан для супружеских пар


Отправить решение Решать в редакторе

Сложность: 85%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 256M

Автор:
Тип задачи
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

На свадьбу в Оше пригласили n супружеских пар. Их рассаживают за круглым дастарханом, вокруг которого стоят 2n подушек, пронумерованных по кругу от 1 до 2n. По традиции хозяина:

  • мужчины и женщины чередуются (рядом с каждым мужчиной сидят две женщины и наоборот);
  • никто не сидит рядом со своим супругом или супругой.

Рисунок

Рассадки различаются, если хотя бы один гость сидит на другой подушке. Для каждого из T вопросов найдите количество рассадок по модулю 10⁹ + 7.

Входные данные

В первой строке — число T (1 ≤ T ≤ 10). В каждой из следующих T строк — одно целое число n (2 ≤ n ≤ 10⁶).

Выходные данные

Для каждого вопроса выведите количество рассадок по модулю 10⁹ + 7.

Пример 1

Вход:

4
2
3
4
5

Выход:

0
12
96
3120

Пояснение

При n = 2 любые двое гостей противоположного пола сидят рядом, поэтому рассадок нет. При n = 3 женщины занимают подушки одной чётности (2 способа) и садятся в любом порядке (3! = 6 способов), после чего мужчин можно посадить единственным образом — всего 12 рассадок.

Система оценивания

Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 10 % тестов n ≤ 6, ещё в 5 % тестов n ≤ 1000.

Подсказка

Задача о супружеских парах (задача Люка). Формула Тушара: после рассадки женщин мужчин можно посадить U(n) = Σ_{k=0}^{n} (−1)^k · 2n / (2n − k) · C(2n − k, k) · (n − k)! способами.


Комментарии

Еще нет ни одного комментария.