题目描述

给定一个长度为 $N$ 的数列 $a$。请问有多少个 $1$ 到 $N$ 的整数的排列 $p$ 满足以下条件？请输出答案对 $10^9+7$ 取模的结果。

• 对于每个 $1 \leq i \leq N$，至少有 $p_i = a_i$ 或 $p_{p_i} = a_i$ 成立。

输入格式

输入通过标准输入给出，格式如下：

$N$ $a_1$ $a_2$ $...$ $a_N$

输出格式

输出满足条件的排列 $p$ 的个数，对 $10^9+7$ 取模。

样例 1

输入

3
1 2 3

输出

4

样例 2

输入

2
1 1

输出

1

样例 3

输入

3
2 1 1

输出

2

样例 4

输入

3
1 1 1

输出

0

样例 5

输入

13
2 1 4 3 6 7 5 9 10 8 8 9 11

输出

6

说明/提示

限制条件

• $1 \leq N \leq 10^5$
• $a_i$ 是整数。
• $1 \leq a_i \leq N$

样例解释 1

共有以下 $4$ 种排列：

• $(1, 2, 3)$
• $(1, 3, 2)$
• $(3, 2, 1)$
• $(2, 1, 3)$

例如，排列 $(1, 3, 2)$ 中，$p_1 = 1$，$p_{p_2} = 2$，$p_{p_3} = 3$。

样例解释 2

只有以下 $1$ 种排列：

• $(2, 1)$

样例解释 3

共有以下 $2$ 种排列：

• $(2, 3, 1)$
• $(3, 1, 2)$

由 ChatGPT 4.1 翻译