题目描述

在本题中，所谓的有根有向树，指的是所有边都从根指向叶子的有根树。

给定一个非负整数序列 $d=(d_1,d_2,\ldots,d_N)$，其总和为 $N-1$。

在编号为 $1$ 到 $N$ 的顶点中，以顶点 $1$ 为根的 $N$ 个顶点的有根有向树中，满足以下条件的树被称为好树：

• 顶点 $i\ (1\leq i \leq N)$ 的出度为 $d_i$。

进一步地，对于好树中的每个顶点 $v$，定义 $f(v)$ 为“顶点 $v$ 的子树中包含的所有顶点（包括 $v$ 本身）编号的最小值”。满足 $f(v)=v$ 的顶点称为好顶点。

请计算所有好树中好顶点的个数之和，并对 $998244353$ 取模后输出。

输入格式

输入通过标准输入给出，格式如下：

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

输出格式

请输出答案。

样例 1

输入

4
2 0 1 0

输出

7

样例 2

输入

10
3 1 0 0 2 0 1 2 0 0

输出

37542

说明/提示

限制条件

• $2 \leq N \leq 500$
• $0 \leq d_i \leq N-1$
• $d_1 \geq 1$
• $\sum_{i=1}^N d_i = N-1$
• 输入的所有数均为整数

样例解释 1

存在如下 $2$ 种好树。被涂成蓝色的顶点为好顶点。

对于每棵树，好顶点的数量分别为 $4$ 和 $3$，因此答案为 $7$。

由 ChatGPT 4.1 翻译