Имеется цепь из $n+1$ узла, пронумерованных от $0$ до $n$ последовательно от одного конца до другого. И-Ай хочет узнать, сколько существует эйлеровых циклов, начинающихся в $0$ и возвращающихся в $0$, таких что количество проходов по ребру $(i-1, i)$ в обоих направлениях в сумме равно $2d_i$. Вам нужно вывести ответ по модулю $998244353$.

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

В первой строке вводится целое положительное число $n$.

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

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

Выведите одно целое число — количество способов по модулю $998244353$.

Ограничения

Для $100\%$ данных гарантируется, что $1\le n,d_i\le 10^5$.

Примеры

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

2
2 1

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

2

Примечание

После первого шага можно выбрать: продолжить движение вперед или вернуться назад, в дальнейшем выбор всегда будет единственным.

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

4
200 30 8 11

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

812059605