Problem Statement

In this problem, a rooted directed tree is a rooted tree where all edges are directed from the root to the leaves.

You are given a sequence of non-negative integers $d=(d_1,d_2,\\ldots,d_N)$ with a sum of $N-1$.

Among the $N$-vertex rooted directed trees with vertex numbered $1$ to $N$ and vertex $1$ as the root, a good tree is one that satisfies the following condition:

• the out-degree of vertex $i\\ (1\\leq i \\leq N)$ is $d_i$.

Furthermore, for a vertex $v$ of a good tree, let $f(v)$ be the minimum vertex number of the vertices (including $v$) in the subtree rooted at vertex $v$, and $v$ is called a good vertex if it satisfies $f(v)=v$.

Find the sum of the numbers of good vertices for all good trees, modulo $998244353$.

Constraints

• $2 \\leq N \\leq 500$
• $0 \\leq d_i \\leq N-1$
• $d_1 \\geq 1$
• $\\sum_{i=1}^N d_i = N-1$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $d_1$ $d_2$ $\\ldots$ $d_N$

Output

Print the answer.

Sample Input 1

4
2 0 1 0

Sample Output 1

7

There are two good trees, as shown below. The blue vertices are good vertices.

For these trees, there are $4$ and $3$ good vertices, respectively, so the answer is $7$.

Sample Input 2

10
3 1 0 0 2 0 1 2 0 0

Sample Output 2

37542