Дастархан для супружеских пар
На свадьбу в Оше пригласили 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)! способами.
Комментарии