There is a chain with $n+1$ vertices, labeled $0, 1, \dots, n$ from one end to the other. Yiai wants to know how many Eulerian circuits starting and ending at $0$ satisfy the condition that the edge $(i-1, i)$ is traversed exactly $2d_i$ times. You only need to output the answer modulo $998244353$.

Input

The first line contains a positive integer $n$.

The next line contains $n$ positive integers, where the $i$-th integer is $d_i$.

Output

Output an integer representing the number of ways modulo $998244353$.

Examples

Input 1

2
2 1

Output 1

2

Note 1

After taking one step, you can choose to continue forward or turn back; subsequently, there is only one unique choice.

Input 2

4
200 30 8 11

Output 2

812059605

Constraints

For $100\%$ of the data, $1 \le n, d_i \le 10^5$.