교환

이 문제에서는 정점 $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, \ldots, a_n$에 대해, 절차를 실행한 뒤 $P[1] = a_1$, $P[2] = a_2$, $\ldots$, $P[n] = a_n$이 되도록 하는 서로 다른 그래프 $G$의 개수를 구하라. 두 그래프는 어떤 정점 쌍 $(u, v)$에 대해 한쪽에만 그 간선이 있으면 서로 다르다. 그래프의 개수가 매우 클 수 있으므로, $998\,244\,353$으로 나눈 나머지를 구하라.

첫 줄에 정수 $n$ ($1 \leq n \leq 500$)이 주어진다.

둘째 줄에 정수 $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq n$)이 주어진다. $1$부터 $n$까지의 각 수는 이 수열에 정확히 한 번씩 나타난다.

조건을 만족하는 그래프 $G$의 개수를 $998\,244\,353$으로 나눈 나머지를 한 줄에 출력한다.