Во время перерывов в подготовке к Международной олимпиаде школьников по информатике маленький Алан любит решать различные головоломки, чтобы развивать мозги. Сегодня он решает головоломку, которая выглядит как таблица \(2 \times n\), где в каждом ряду записана перестановка чисел \(1,2,3,\ldots,n\).
Задача головоломки — сделать так, чтобы ни в каком ряду и ни в каком столбце не было двух одинаковых чисел (назовем такие состояния решенными), а единственная разрешенная операция — поменять местами два числа в одном столбце. Когда маленький Алан решил головоломку много раз, он заскучал и начал размышлять, а сколько вообще существует различных решенных состояний в данной головоломке, которые он может получить из некоторого начального решенного состояния, применяя только разрешенные операции?
Маленький Алан не справился с этой сложной задачей, поэтому он попросил вас помочь ему. Найдите ответ по модулю \(10^9+7\).
Выходные данные
Для каждого набора входных данных выведите одно целое число — количество решенных состояний головоломки, которые можно получить из данного, меняя местами числа в столбцах. Так как ответ может быть большим, выведите его по модулю \(10^9+7\).
Примечание
Два возможных решенный состояния в примере \(1\):
- \([1,4,2,3]\) в первой строке, и \([3,2,1,4]\) во второй,
- \([3,2,1,4]\) в первой строке, и \([1,4,2,3]\) во второй.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
4
1 4 2 3
3 2 1 4
8
2 6 5 1 4 3 7 8
3 8 7 5 1 2 4 6
|
2
8
|