Для перестановки \(p\) чисел от \(1\) до \(n\) мы можем задать лестничный массив \(a\) следующим образом: \(a_i\) равняется длине наибольшего подотрезка перестановки, который содержит позицию \(i\) и состоит из последовательных чисел в отсортированном порядке: \([x, x+1, \ldots, y-1, y]\) или \([y, y-1, \ldots, x+1, x]\) для некоторых \(x \leq y\). Например, для перестановки \(p = [4, 1, 2, 3, 7, 6, 5]\) получается лестничный массив \(a = [1, 3, 3, 3, 3, 3, 3]\).
Вам дан массив \(a\). Ваша задача — посчитать количество перестановок, лестничный массив которых равен \(a\). Так как это количество может быть достаточно большим, посчитайте его по модулю \(998\,244\,353\). Обратите внимание, что количество может быть равно нулю.
Выходные данные
Выведите количество перестановок, лестничный массив которых равен \(a\). Так как это число может быть довольно большим, выведите его по модулю \(998\,244\,353\).