Загадана какая-то перестановочка длины \(n\).
Вам даны индексы её префиксных максимумов и суффиксных максимумов.
Напомним, что перестановка длины \(k\) — это такой массив размера \(k\), что в нем встречается каждое целое число от \(1\) до \(k\) ровно один раз.
Префиксные максимумы — элементы, которые являются максимумом на префиксе, заканчивающемся в этом элементе. Более формально, элемент \(a_i\) является префиксным максимумом, если \(a_i > a_j\) для каждого \(j < i\).
Аналогично определяются суффиксные максимумы, элемент \(a_i\) является суффиксным максимумом, если \(a_i > a_j\) для каждого \(j > i\).
Требуется вывести количество различных перестановок, которые могли бы быть загаданы.
Так как это число может быть очень большим, выведите ответ по модулю \(10^9 + 7\).
Примечание
Во втором наборе входных данных подходят следующие перестановки:
- \([1, 4, 3, 2]\)
- \([2, 4, 3, 1]\)
- \([3, 4, 2, 1]\)
В шестом наборе входных данных подходят следующие перестановки:
- \([2, 1, 6, 5, 3, 4]\)
- \([3, 1, 6, 5, 2, 4]\)
- \([3, 2, 6, 5, 1, 4]\)
- \([4, 1, 6, 5, 2, 3]\)
- \([4, 2, 6, 5, 1, 3]\)
- \([4, 3, 6, 5, 1, 2]\)
- \([5, 1, 6, 4, 2, 3]\)
- \([5, 2, 6, 4, 1, 3]\)
- \([5, 3, 6, 4, 1, 2]\)
- \([5, 4, 6, 3, 1, 2]\)