题目描述

给定一个正整数 $n$ 和一个长度为 $n+1$ 的序列 $lim_0,lim_1,lim_2,\dots,lim_n$，求长度为 $n+1$ 的整数序列 $f_0,f_1,f_2,\dots,f_n$ 的方案数，使得以下条件成立。

• 对于所有 $0\le i\le n$，有 $0\le f_i\le lim_i$。
• 对于任意 $0\le m\le n$ 满足，对于所有 $0\le i\le m$，有 $f_{f_i+f_{m-i}}=f_m$。（当 $i>n$ 时，$f_i=-1$）

答案对 $998244353$ 取模。

输入格式

输入共两行。

第一行一个正整数 $n$，表示序列长度为 $n+1$。

第二行 $n+1$ 个正整数，分别表示 $lim_0,lim_1,\dots,lim_n$。

输出格式

输出共一行。

第一行一个整数，表示符合要求的序列个数对 $998244353$ 取模的结果。

样例一

input

2
2 2 2

output

6

explanation

符合要求的方案有：[0,0,0],[0,1,0],[0,1,1],[0,1,2],[1,0,1],[1,1,1]。

样例二

input

5
1 1 4 5 1 4

output

8

样例三

input

10
0 1 2 3 4 5 6 7 8 9 10

output

56

数据范围

下发文件中有 Unix 格式的样例。

对于 $100\%$ 的数据，有 $1\le n\le 2000, 0\le lim_i\le n$。

共 $20$ 个测试点，各个测试点的数据范围如下：

测试点编号	$n\le$	其他约束
$1$		无
$2$	$5$
$3$	$15$
$4$	$30$
$5$	$50$
$6$	$70$
$7$	$100$
$8$	$200$
$9$	$100$	$lim_0=0$
$10$	$500$
$11$	$2000$
$12$		$lim_0=0$ 且 $lim_i\le 5$
$13$		$lim_i\le 5$
$14$		$lim_i\le 20$
$15\sim 16$		$lim_i=i$
$17\sim 20$		无