题目描述

给定一个长为 $n$ 的非负整数序列 $A=\{a_1,a_2,\dots,a_n\}$。

定义 $A$ 的一个划分 $D=\{d_1,d_2,\cdots,d_k,d_{k+1}\}(1=d_1<d_2<\cdots<d_k<d_{k+1}=n+1)(\forall 1\le i\le n,d_i\in \mathbb{Z})$ 将 $A$ 分为 $S_1=\{A_{d_1},A_{d_1+1},\cdots,A_{d_2-1}\}$，$S_2=\{A_{d_2},A_{d_2+1},\cdots,A_{d_3-1}\}$，$\cdots$，$S_k=\{A_{d_k},A_{d_k+1},\cdots,A_{d_{k+1}-1}\}$ 这 $k$ 个集合。

定义一个集合 $S$ 的 $\operatorname{mex}$ 函数：$\operatorname{mex}(S)=\min_{x\in \mathbb{N},x\notin S} x$。

定义一个划分 $D$ 的权值 $f(D)=\prod_{i=1}^k\operatorname{mex}(S_i)$。

记 $U=\sum_D f(D)$。

求 $U \bmod 998244353$。

输入格式

从文件 divide.in 中读入数据。

第一行输入一个正整数 $n$ 表示序列 $A$ 的长度。

接下来一行，输入 $n$ 个非负整数，第 $i$ 个非负整数表示 $a_i$。

输出格式

输出到文件 divide.out 中。

输出一个非负整数表示答案。

样例

样例输入 1

4
0 1 0 2

样例输出 1

8

样例解释 1

一共有 $8$ 个划分 $D$：$\{1,5\}$，$\{1,4,5\}$，$\{1,3,5\}$，$\{1,3,4,5\}$，$\{1,2,5\}$，$\{1,2,4,5\}$，$\{1,2,3,5\}$，$\{1,2,3,4,5\}$。

它们的权值分别为：$3$，$2\times 0=0$，$2\times 1=2$，$2\times 1\times 0=0$，$1\times 3=3$，$1\times 2\times 0=0$，$1\times 0\times 1=0$，$1\times 0\times 1\times 0=0$。

于是 $U=3+0+2+0+3+0+0+0=8$。

故 $U\bmod 998244353=8$，故输出 $8$。

样例 2

见附加文件中的 divide2.in 与 divide2.ans。

样例 3

见附加文件中的 divide3.in 与 divide3.ans。

该样例满足 $a_i\le 10$。

样例 4

见附加文件中的 divide4.in 与 divide4.ans。

数据范围与提示

对于 $10\%$ 的数据，$n\le 20$。
对于 $30\%$ 的数据，$n\le 3000$。
对于 $60\%$ 的数据，$n\le 10^5$。
另有 $20\%$ 的数据，$a_i\le 10$。
对于 $100\%$ 的数据，$1\le n\le 10^6$，$0\le a_i\le 10^9$。