暂无测试数据。

小 $\mathcal{L}$ 有一个栈和一个队列，现在队列中有 $n$ 个不同元素，每次可以选择两种操作：

1. 把队头的元素放到栈顶（如果队列为空则不能进行该操作）
2. 把栈顶元素放入输出数组（如果栈为空则不能进行该操作）

现在总共要进行 $2n$ 次操作，故输出数组长度必然为 $n$。

小 $\mathcal{L}$ 有强迫症，所以输出数组的第一个位置的元素有必须是自己喜欢的。

现在给出队列（$a_1\sim a_n$ 其中 $a_1$ 为队头）中的元素的属性（$a_i$ 为 $1$ 则表示该元素小 $\mathcal{L}$ 喜欢，为 $0$ 则不喜欢），您需要求出符合小 $\mathcal{L}$ 要求的不同的出栈入栈方式的个数，因为结果很大，所以您只需要给出结果 $\bmod 998244353$ 后的结果即可。

输入格式

输入包含两行。

第一行输入一个正整数 $n$。

第二行输入 $n$ 个正整数 $a_1,a_2,...,a_n$。

输出格式

输出一个正整数表示答案。

数据范围

对于 $20\%$ 的数据 $n\leq 10$。

对于 $40\%$ 的数组 $n\leq 2333$。

对于另外 $20\%$ 的数据仅存在 $a_1$ 的值为 $1$。

对于另外 $20\%$ 的数据仅存在唯一的 $i$，使得 $a_i=1$。

对于 $100\%$ 的数据 $n\leq1\times 10^6$，$a_i\in\{0,1\}$。

3
1 0 1

3

5
1 0 1 0 1

24