题目描述

设 $S$ 为由 $1$ 到 $N$ 的所有整数构成的集合。

$f$ 是一个从 $S$ 到 $S$ 的函数，$f(1),\ f(2),\ \cdots,\ f(N)$ 的值分别为 $f_1,\ f_2,\ \cdots,\ f_N$。

请计算满足以下两个条件的 $S$ 的非空子集 $T$ 的个数，并将结果对 $998244353$ 取模：

• 对于所有 $a \in T$，都有 $f(a) \in T$。
• 对于所有 $a, b \in T$，若 $a \neq b$，则 $f(a) \neq f(b)$。

输入格式

输入以如下格式从标准输入给出：

$N$ $f_1$ $f_2$ $\ldots$ $f_N$

输出格式

输出满足条件的 $S$ 的非空子集的个数，对 $998244353$ 取模后的结果。

样例 1

输入

2
2 1

输出

1

样例 2

输入

2
1 1

输出

1

样例 3

输入

3
1 2 3

输出

7

说明/提示

限制条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq f_i \leq N$
• 输入均为整数

样例解释 1

$f(1) = 2,\ f(2) = 1$。由于 $f(1) \neq f(2)$，第二个条件总是满足，但根据第一个条件，$1$ 和 $2$ 必须同时包含在 $T$ 中。

样例解释 2

$f(1) = f(2) = 1$。由于第一个条件，$1$ 必须属于 $T$，而根据第二个条件，$2$ 不能属于 $T$。

样例解释 3

$f(1) = 1,\ f(2) = 2,\ f(3) = 3$。第一个和第二个条件始终满足，因此 $S$ 的所有非空子集都满足条件。

由 ChatGPT 4.1 翻译