Ване попался на глаза подарок с какого-то его предыдущего дня рождения, это массив размера \(n\) из целых чисел от \(1\) до \(200\). Массив немного истрепался, и некоторые числа нельзя разобрать. Ваня помнит, что для любого числа в массиве хотя бы один из его соседей не меньше его, более формально:
\(a_{1} \le a_{2}\),
\(a_{n} \le a_{n-1}\) и
\(a_{i} \le max(a_{i-1}, \,\, a_{i+1})\) для всех \(i\) от \(2\) до \(n-1\).
Ваня не помнит массив и попросил вас найти количество различных способов восстановить массив. Восстановленные элементы массива также должны быть целыми числами от \(1\) до \(200\). Поскольку это число может быть довольно большим, выведите его по модулю \(998244353\).
Выходные данные
Выведите одно целое число — количество способов восстановить массив по модулю \(998244353\).
Примечание
В первом примере единственное возможное значение \(a_{2}\) — \(2\).
Во втором примере \(a_{1} = a_{2}\), следовательно различных значений ровно \(200\), так как все восстановленные значения должны быть целыми числами от \(1\) до \(200\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 -1 2
|
1
|
|
2
|
2
-1 -1
|
200
|