F. Медуза и OEIS
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Медуза всегда использует 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]$$$.