Momoka's Fate

Momoka had a life defined by n life‐changing events numbered from 1 to n. Her destiny was originally given by a permutation p = [\(p_1, p_2, \dots, p_n\)] (although p is not necessarily a permutation in the input). For each event i (\(1 \le i \le n\)), the intended fate was that event i would affect event \(p_i\). However, because of Momoka’s unusual ability, the course of her life may deviate from the destined path. In her diary she recorded a sequence that tells, immediately after experiencing event i, which event was affected – the diary is a sequence p as well, whose i-th entry is \(p_i\).

Ringo, having gotten hold of the diary, now wishes to know how many possible original destinies (i.e. permutations \(a = [a_1,a_2,\dots,a_n]\) of \(\{1,2,\dots,n\}\)) could have produced a situation where for every \(1 \le i \le n\) the following condition holds:

[ \text{(,(a_i = p_i),)} \quad \text{or} \quad \text{((a_{p_i}= i))} \quad (1 \le i \le n). ]

More precisely, you are given a sequence \(p_1, p_2, \dots, p_n\) with \(1 \le p_i \le n\) (which is not necessarily a permutation). Determine the number of permutations \(a_1, a_2, \dots, a_n\) of \(\{1, 2, \dots, n\}\) satisfying that for every \(1 \le i \le n\),

[ a_i=p_i \quad \text{or} \quad a_{p_i}=i. ]

Since the answer can be large, output it modulo 998244353.

Note: It turns out that a valid permutation exists only if p itself is a permutation; if not, the answer is 0. If \(p\) is indeed a permutation then one may show that the only freedom lies in the cycles of \(p\) with length \(\ge 3\). In particular, if one decomposes \(p\) into cycles then each fixed point (cycle of length 1) and each 2-cycle forces a unique assignment, while every cycle of length at least 3 gives exactly 2 possibilities. Therefore the answer is \(2^{c}\) modulo 998244353, where c is the number of cycles of \(p\) with length \(\ge3\) (and if p is not a permutation, the answer is 0).

inputFormat

The input consists of two lines. The first line contains a single integer n (the number of events). The second line contains n space‑separated integers: \(p_1, p_2, \dots, p_n\), where \(1 \le p_i \le n\).

outputFormat

Output a single integer — the number of valid permutations \(a_1,a_2,\dots,a_n\) satisfying the condition, taken modulo 998244353.

sample

2
1 2

1