/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
この問題では、根付き有向木と言った際には全ての辺が根から葉の方向に向き付けられた根付き木を指すものとします。
総和が N-1 であるような非負整数列 d=(d_1,d_2,\ldots,d_N) が与えられます。
頂点に 1 から N の番号がついた、頂点 1 を根とする N 頂点の根付き有向木のうち、以下の条件を満たすものを良い木と呼びます。
- 頂点 i\ (1\leq i \leq N) の出次数は d_i
さらに、良い木の頂点 v に対して、 f(v) を「頂点 v の部分木に含まれる頂点（v 含む）の頂点番号の最小値」と定め、f(v)=v を満たす頂点を良い頂点と呼びます。
良い木全てに対する良い頂点の個数の総和を 998244353 で割ったあまりを求めてください。
制約
- 2 \leq N \leq 500
- 0 \leq d_i \leq N-1
- d_1 \geq 1
- \sum_{i=1}^N d_i = N-1
- 入力される数値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N d_1 d_2 \ldots d_N
出力
答えを出力せよ。
入力例 1
4 2 0 1 0
出力例 1
7
良い木は以下の 2 通りあります。青く塗られた頂点は良い頂点です。
それぞれについて良い頂点は 4 個、 3 個なので答えは 7 です。
入力例 2
10 3 1 0 0 2 0 1 2 0 0
出力例 2
37542
Score : 700 points
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