Description

大魔法师波波王拥有使用大名鼎鼎的消失魔法的能力。只要他轻轻挥动魔法棒，他就可以让趣味赛最难的题目消失（除了这道题）。猫猫虫 capoo 想学习消失魔法，这样它就可以在趣味赛上 AK 啦！于是它找到了波波王，拜他为师，成为了波波王的弟子。然而，学习消失魔法没有那么简单。capoo 每天还未破晓便起床训练，直到万籁俱寂之时才休息。努力总有回报。这天，capoo 终于学会了最简单的消失魔法——删去一个数！于是大魔法师波波王便决定给 capoo 安排一场试炼。

波波王给了 capoo 一个长为 $n$ 的排列。为了检验 capoo 的消失魔法，波波王让 capoo 每次删掉这个数列左右两端当中较大的那个数，直到最终只剩下一个数。

假设删除最左端的数记为 $0$，删除最右端的数记为 $1$，那么一个排列经过上述操作可以映射到一个删除序列上，比如排列 $p=\{3,1,2,4,5\}$ 可以映射到删除序列 $a=\{1,1,0,1\}$ 上。最终的试炼是：给出一个删除序列，求出有多少个排列可以映射到这个删除序列上？

「ん?」capoo 虽然有超强的记忆力，可以记住每次操作的顺序，但是它的逻辑推理能力还未出神入化，于是它看向了你，希望你可以帮助它完成最终的试炼。

如果一个长为 $n$ 的序列中只包含从 $1$ 到 $n$ 的整数，并且每个整数在序列中只出现一次，则称这个序列为一个长为 $n$ 的排列。例如 $\{1,2,3\},\{3,5,2,4,1\}$ 是排列，而 $\{1,3,4\},\{2,3,3,3\}$ 不是排列。

Input

第一行一个整数 $n\ (2\le n\le 10^6)$，表示排列的长度。

第二行 $n-1$ 个整数，表示删除序列。其中第 $i$ 个数 $a_i=0$ 表示第 $i$ 个操作是删除最左边的数，$a_i=1$ 表示第 $i$ 个操作是删除最右边的数。

Output

一行一个整数，表示满足题意的排列数量，由于这个数量很大，请输出它对 $998244353$ 取模后的值。

Samples

5
1 1 0 1

2

Note

第一次和第二次操作删除最右边的数，第三次操作删除最左边的数，第四次操作删除最右边的数，满足题意的排列有 $\{3,1,2,4,5\}$ 以及 $\{3,1,2,5,4\}$，共 $2$ 种。

Resources

电子科技大学第十四届 ACM 趣味程序设计竞赛