在本题中，我们关注的是具有 $n$ 个顶点的无向图，顶点编号为 $1$ 到 $n$，且图中没有自环和重边。

对于给定的图 $G$，可以执行以下过程：

function dfs(u) {
set u to active
for v in 1, 2, ..., n
if (u and v are adjacent in G) and (v is inactive) {
swap P[u] and P[v]
dfs(v)
}
set u to done
}

for u in 1, 2, ..., n {
set u to inactive
set P[u] to u
}

for u in 1, 2, ..., n
if u is inactive:
dfs(u)

给定 $a_1, a_2, \dots, a_n$，求满足以下条件的图 $G$ 的数量：在执行上述过程后，$P[1] = a_1, P[2] = a_2, \dots, P[n] = a_n$。如果两个图存在一对顶点 $(u, v)$，使得其中一个图包含边 $(u, v)$ 而另一个图不包含，则认为这两个图是不同的。由于满足条件的图的数量可能非常大，请输出其对 $998\,244\,353$ 取模的结果。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 500$)。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$)。保证 $1$ 到 $n$ 中的每个数字在序列中恰好出现一次。

输出格式

输出一个整数：满足条件的图 $G$ 的数量，对 $998\,244\,353$ 取模。

样例

样例输入 1

3
2 3 1

样例输出 1

2

样例输入 2

9
7 2 9 1 3 8 6 5 4

样例输出 2

3528