#arc162d. [arc162_d]Smallest Vertices

[arc162_d]Smallest Vertices

题目描述

在这个问题中,根据以下规则定义一个有根有向树:

给定一个非负整数序列 d=(d1,d2,ldots,dN)d=(d_1,d_2,\\ldots,d_N),其中 dd 的和为 N1N-1

对于从 11NN 编号的顶点和以顶点 11 为根的有根有向树,满足以下条件的树称为好树

  • 顶点 i(1leqileqN)i\\ (1\\leq i \\leq N) 的出度是 did_i

对于好树的顶点 vv,令 f(v)f(v) 表示以顶点 vv 为根的子树中顶点的最小编号(包括 vv 自身)。如果顶点 vv 满足 f(v)=vf(v)=v,则称其为好顶点

求所有好树中好顶点的编号之和,对 998244353998244353 取模的结果。

约束条件

  • 2leqNleq5002 \\leq N \\leq 500
  • 0leqdileqN10 \\leq d_i \\leq N-1
  • d1geq1d_1 \\geq 1
  • sumi=1Ndi=N1\\sum_{i=1}^N d_i = N-1
  • 所有输入值都是整数。

输入

从标准输入读取输入,其格式如下:

NN d1d_1 d2d_2 ldots\\ldots dNd_N

输出

输出答案。


示例输入 1

4
2 0 1 0

示例输出 1

7

有两个好树,如下所示。蓝色的顶点是好顶点。

对于这两棵树,分别有 4433 个好顶点,因此答案为 77


示例输入 2

10
3 1 0 0 2 0 1 2 0 0

示例输出 2

37542