Медуза всегда использует OEIS для решения математических задач, но сейчас она нашла задачу, которую нельзя решить с помощью OEIS:
Подсчитайте количество перестановок \(p\) из \([1, 2, \dots, n]\) таких, что для всех \((l, r)\) таких, что \(l \leq r \leq m_l\), подмассив \([p_l, p_{l+1}, \dots, p_r]\) не является перестановкой \([l, l+1, \dots, r]\).
Поскольку ответ может быть большим, необходимо найти ответ по модулю \(10^9+7\).
Примечание
В первом примере условию удовлетворяют \([2, 3, 1]\) и \([3, 1, 2]\).