Yana、Mino、White 和 Huzz 是最好的朋友。

在终于完成了教练苛刻的任务后，Huzz 赢得了休息的机会。在一个慵懒的下午，世界似乎慢了下来，笼罩在即将来临的黄昏那温暖、金色的薄雾中。微风轻拂，仅仅吹动了在穿过大橡树叶子的阳光中翩翩起舞的微尘。

在这个昏昏欲睡、舒适的空闲中，Huzz 在他的软鲨鱼玩具里发现了一个排列。他决定和朋友们分享这个排列以寻找乐趣。

Mino 喜欢拆分。他可以将这个排列拆分为若干个连续的段。

Yana 喜欢交换。他可以选择一个连续的段，并交换其中的最大值和最小值。

具体来说，他们可以按任意顺序执行以下两种操作任意次：

• 拆分（split）：选择一个长度大于 1 的连续段。然后在其内部选择一个位置，将其拆分为两个相邻的连续段。例如，$(a_i, \dots, a_j)$ 可以被拆分为 $(a_i, \dots, a_k)$ 和 $(a_{k+1}, \dots, a_j)$，其中 $i \le k < j$。
• 交换（swap）：选择一个连续段，并交换其中的最大值和最小值。

在执行任意次数的操作后，他们停止操作，并将所有得到的段按其原始顺序合并，从而形成一个新的排列。

White 喜欢计数。她想知道——他们总共可以得到多少个不同的排列？

由于结果可能非常大，你只需要求出答案对 998 244 353 取模后的结果。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 500$)，表示排列的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$)，表示排列本身。保证 $\{a_n\}$ 是一个排列。

输出格式

输出一个整数，表示他们可以得到的不同排列的数量对 998 244 353 取模后的结果。

样例

输入样例 1

4
1 4 2 3

输出样例 1

10

输入样例 2

7
5 1 4 2 6 3 7

输出样例 2

340

说明

在第一个样例中，以下是所有可能得到的排列：

(1234), (1243), (1423), (1432), (4123), (4132), (4213), (4231), (4312), (4321)