Дан правильный $n$-угольник. Помимо $n$ вершин самого многоугольника, на $i$-й стороне по часовой стрелке расположены дополнительные $a_i-1$ вершин, которые делят эту сторону на равные части. Иными словами, $i$-й отрезок разделен вершинами на $a_i$ равных сегментов.

Вы можете соединять вершины отрезками. После проведения всех отрезков любые два добавленных отрезка могут пересекаться только в своих концах. Кроме того, новые отрезки не должны совпадать со сторонами исходного многоугольника.

Мы называем полученный после добавления отрезков граф триангуляцией тогда и только тогда, когда каждая грань внутри многоугольника является треугольником. Заметьте, что на сторонах треугольника могут находиться вершины, лежавшие на сторонах исходного выпуклого многоугольника.

Для заданного выпуклого многоугольника определите количество способов его триангуляции, удовлетворяющих вышеуказанным условиям. Выведите ответ по модулю $998\,244\,353$.

Входные данные

В первой строке вводится целое число $n$, количество сторон выпуклого многоугольника.

Во второй строке вводятся $n$ целых положительных чисел, где $i$-е число равно $a_i$, как описано в условии задачи.

Выходные данные

Выведите одно целое число — количество способов триангуляции, удовлетворяющих условиям задачи, по модулю $998\,244\,353$.

Примеры

Пример 1

Входные данные

3
2 2 1

Выходные данные

5

Примечание 1

$5$ способов показаны на рисунке.

Пример 2

Входные данные

5
3 1 4 2 5

Выходные данные

359895

Пример 3

Входные данные

8
4 2 1 8 3 7 3 1

Выходные данные

577596154

Подзадачи

Для $10\%$ данных гарантируется, что $\sum a_i \leq 300$.

Для $50\%$ данных гарантируется, что $\sum a_i \leq 5\,000$.

Для $100\%$ данных гарантируется, что $n \geq 3$, $a_i \geq 1$, $\sum a_i \leq 5 \times 10^5$.