如果 $$$a_1 = k - 1$$$ 且 $$$a_1 > 0$$$,则整数序列 $$$a_1, a_2, \dots, a_k$$$ 称为良好数组。例如,序列 $$$[3, -1, 44, 0], [1, -99]$$$ 是好的数组,而序列 $$$[3, 7, 8], [2, 5, 4, 1], [0]$$$ — 则不是。
如果一个整数序列可以分为正数个好的数组,则该序列被称为好的。每个好的数组应该是序列的一个子段,并且序列的每个元素都应该恰好属于一个数组。例如,序列 $$$[2, -3, 0, 1, 4]$$$, $$$[1, 2, 3, -3, -9, 4]$$$ 是好的,而序列 $$$[2, -3, 0, 1]$$$, $$$[1, 2, 3, -3 -9, 4, 1]$$$ — 则不好。
对于给定的数字序列,计算其为好序列的子序列的数量,并以 998244353 为模打印此类子序列的数量。
输入
第一行包含数字 $$$n~(1 \le n \le 10^3)$$$ — 初始序列的长度。下面一行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n~(-10^9 \le a_i \le 10^9)$$$ — 序列本身。
输出
在单行中输出一个整数——原始序列中好序列的子序列数,以 998244353 为模。
示例
输入 #1
3 2 1 1
输出 #1
2
输入 #2
4 1 1 1 1
输出 #2
7
注意
在第一个测试用例中,有两个好的子序列 - $$$[a_1, a_2, a_3]$$$ 和 $$$[a_2, a_3]$$$。
在第二个测试用例中,七个好的子序列 - $$$[a_1, a_2, a_3, a_4], [a_1, a_2], [a_1, a_3], [a_1, a_4], [a_2, a_3], [a_2, a_4]$$$ 和 $$$[a_3, a_4]$$$。