Nikuniku 今天学习了选择排序。为了更好地理解这个算法，她重新实现了它，并计算了每一轮的交换次数，如下面的伪代码所示：

Algorithm 1 Selection Sort
1: function Sort(Permutation P)
2: for i in [1, n − 1] do
3: ci ← 0
4: for j in [i + 1, n] do
5: if Pi > Pj then
6: swap(Pi, Pj)
7: ci ← ci + 1

Nikuniku 想知道有多少种不同的长度为 $n$ 的排列 $P$，使得在运行该算法后，每一轮的交换次数（伪代码中的计数器 $c_i$）与给定的 $t_1, \dots, t_{n-1}$ 相匹配。你只需要输出答案对 $998244353$ 取模的结果。长度为 $n$ 的排列由 $1, \dots, n$ 恰好各出现一次组成。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 2 \cdot 10^5$)。

接下来一行包含 $n-1$ 个整数 $t_1, \dots, t_{n-1}$。保证至少存在一个满足要求的排列。

输出格式

输出答案对 $998244353$ 取模的结果。

样例

样例输入 1

3
1 1

样例输出 1

2

样例输入 2

6
0 1 1 1 0

样例输出 2

4

样例输入 3

6
0 1 2 1 1

样例输出 3

6