Dividing Chains
对于一个序列 z1,z2,…,zn,考虑集合 S={1,n+1}。小青鱼可以执行以下操作恰好 n−1 次:
- 选择一个整数 x,满足 x∈/S 且 1<x≤n。
- 令 l 为 x 在 S 中的前驱,即 S 中小于 x 的最大整数。
- 令 r 为 x 在 S 中的后继,即 S 中大于 x 的最小整数。
- 选择不做任何改变,或者对序列 z 执行以下更新:将子段 zl,zl+1,…,zr−1 整体反转,即对所有 l≤i≤r−1,同时令原 zi 移到位置 r−1−(i−l)。
- 更新 S←S∪{x}。
显然,最后 S 会变为 {1,2,…,n,n+1}。
给定一个单调不降的序列 a1,a2,…,an,请计算有多少个不同的序列 z1,z2,…,zn 满足:存在一种执行上述操作的方法,能够将 z 变成 a。输出这个数量对 998244353 取模的结果。
这个问题让小青鱼感到莫名其妙,于是他请你来解决。
输入格式
输入仅包含一组数据。
第一行包含一个整数 n(1≤n≤500)。
第二行包含 n 个整数 a1,a2,…,an,保证
1≤a1≤a2≤⋯≤an≤n.
输出格式
输出一行一个整数,表示满足条件的不同序列的数量对 998244353 取模的结果。
原样例 1
3
2 3 3
3
原样例 2
5
1 1 3 3 5
29
原样例 3
9
1 2 3 5 5 6 7 8 9
26276