题目描述

给定一个正整数 $ 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 $ 个测试点，各个测试点的数据范围如下：