对于一个序列 $z_1, z_2, \dots, z_n$，考虑集合 $S = \{1, n+1\}$。Little Cyan Fish 可以执行恰好 $n-1$ 次以下操作：

• 选择一个整数 $x$，满足 $x \notin S$ 且 $1 < x \le n$。
• 令 $l$ 为 $x$ 在 $S$ 中的前驱，即 $S$ 中满足 $l < x$ 的最大整数。
• 令 $r$ 为 $x$ 在 $S$ 中的后继，即 $S$ 中满足 $x < r$ 的最小整数。
• 不进行任何操作，或者对序列 $z$ 执行以下更新：
  • 翻转子段 $z_l, z_{l+1}, \dots, z_{r-1}$，即对于所有 $l \le i \le r-1$，将 $z_i$ 变为 $z_{r-1-(i-l)}$。
• 更新 $S \leftarrow S \cup \{x\}$。

显然，最终 $S$ 将变为 $\{1, 2, \dots, n, n+1\}$。对于给定的单调非递减序列 $a_1, a_2, \dots, a_n$，你需要计算满足以下条件的序列 $z_1, z_2, \dots, z_n$ 的数量（对 $998\,244\,353$ 取模）：

• 存在一种应用上述操作的方法，将序列 $z_1, z_2, \dots, z_n$ 转换为 $a_1, a_2, \dots, a_n$。

这个问题对 Little Cyan Fish 来说听起来毫无意义。因此，他请求你来解决这个问题。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 500$)。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_1 \le a_2 \le \dots \le a_n \le n$)。

输出格式

输出一行，包含一个整数，表示答案对 $998\,244\,353$ 取模的结果。

样例

样例输入 1

3
2 3 3

样例输出 1

3

样例输入 2

5
1 1 3 3 5

样例输出 2

29

样例输入 3

9
1 2 3 5 5 6 7 8 9

样例输出 3

26276