В простой версии задачи \(a_i\) находятся в диапазоне \([0, n]\); в сложной версии \(a_i\) находятся в диапазоне \([-1, n]\) и определение хорошей перестановки немного отличается. Вы можете делать взломы, только если обе версии задачи решены.
Вам дано целое число \(n\) и массив \(a_1, a_2 \dots, a_n\) целых чисел в диапазоне \([0, n]\).
Перестановка \(p_1, p_2, \dots, p_n\) элементов \([1, 2, \dots, n]\) называется хорошей, если для каждого \(i\) верно следующее утверждение:
- количество значений \(\leq i\) в \([p_1, p_2, \dots, p_i]\) в точности равно \(a_i\).
Посчитайте количество хороших перестановок \([1, 2, \dots, n]\) по модулю \(998\,244\,353\).
Выходные данные
Для каждого набора входных данных выведите одну строку, содержащую количество хороших перестановок по модулю \(998\,244\,353\).
Примечание
В первом наборе входных данных единственной хорошей перестановкой является \([1, 2, 3, 4, 5]\).
Во втором наборе входных данных существует \(4\) хороших перестановки: \([2, 1, 5, 6, 3, 4]\), \([2, 1, 5, 6, 4, 3]\), \([2, 1, 6, 5, 3, 4]\), \([2, 1, 6, 5, 4, 3]\). Например, \([2, 1, 5, 6, 3, 4]\) — хорошая, потому что:
- \(a_1 = 0\), и в \([p_1] = [2]\) есть \(0\) значений \(\leq 1\);
- \(a_2 = 2\), и есть \(2\) значения \(\leq 2\) в \([p_1, p_2] = [2, 1]\);
- \(a_3 = 2\), и есть \(2\) значения \(\leq 3\) в \([p_1, p_2, p_3] = [2, 1, 5]\);
- \(a_4 = 2\), и есть \(2\) значения \(\leq 4\) в \([p_1, p_2, p_3, p_4] = [2, 1, 5, 6]\);
- \(a_5 = 4\), и есть \(4\) значения \(\leq 5\) в \([p_1, p_2, p_3, p_4, p_5] = [2, 1, 5, 6, 3]\);
- \(a_6 = 6\), и есть \(6\) значений \(\leq 6\) в \([p_1, p_2, p_3, p_4, p_5, p_6] = [2, 1, 5, 6, 3, 4]\).
В третьем наборе входных данных нет хороших перестановок, потому что не существует перестановок с \(a_6 = 5\) значениями \(\leq 6\) в \([p_1, p_2, p_3, p_4, p_5, p_6]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
5
1 2 3 4 5
6
0 2 2 2 4 6
6
0 1 3 4 5 5
6
1 2 3 2 4 6
15
0 0 1 1 1 2 3 4 5 6 7 9 11 13 15
|
1
4
0
0
532305727
|