Codeforces Round 901 (Div. 1) |
---|
Закончено |
Медуза всегда использует 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$$$.
Первая строка ввода содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 200$$$) — длину перестановки.
Вторая строка ввода содержит $$$n$$$ целых чисел $$$m_1, m_2, \dots, m_n$$$ ($$$0 \leq m_i \leq n$$$).
Выведите количество различных перестановок, удовлетворяющих условиям, по модулю $$$10^9+7$$$.
3 1 2 3
2
5 2 4 3 4 5
38
5 5 1 1 1 1
0
В первом примере условию удовлетворяют $$$[2, 3, 1]$$$ и $$$[3, 1, 2]$$$.
Название |
---|