Это сложная версия задачи. Единственное различие между двумя версиями — ограничение на \(n\). Вы можете делать взломы, только если все версии задачи решены.
Назовем массив \(a\) нечетной длины \(2m+1\) (при \(m \ge 1\)) плохим, если элемент \(a_{m+1}\) равен медиане этого массива. Другими словами, массив является плохим, если после его сортировки элемент на \(m+1\)-й позиции остается неизменным.
Назовем перестановку \(p\) целых чисел от \(1\) до \(n\) анти-медианной, если каждый ее подмассив нечетной длины \(\ge 3\) не является плохим.
Вам уже даны значения некоторых элементов перестановки. Найдите количество способов задать неизвестные значения, чтобы получить анти-медианную перестановку. Поскольку это число может быть очень большим, найдите его по модулю \(10^9+7\).
Выходные данные
Для каждого наборам входных данных выведите одно целое число — количество способов установить неизвестные значения для получения анти-медианной перестановки, по модулю \(10^9+7\).
Примечание
В первом наборе входных данных анти-медианными являются как \([1, 2]\), так и \([2, 1]\).
Во втором наборе входных данных перестановки \([1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2]\) являются анти-медианными. Оставшиеся две перестановки, \([1, 2, 3]\), \([3, 2, 1]\), сами по себе являются плохими массивами, так как их медиана, \(2\), находится в их середине.
В третьем наборе входных данных \([1, 2, 3, 4]\) не является анти-медианным, поскольку содержит плохой подмассив \([1, 2, 3]\).
В четвертом наборе входных данных единственный анти-медианный массив, который можно получить, это \([5, 6, 3, 4, 1, 2]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2
-1 -1
3
-1 -1 -1
4
1 2 3 4
6
-1 -1 3 4 -1 -1
8
-1 -1 -1 -1 -1 -1 -1 -1
|
2
4
0
1
316
|