← 返回题目列表

AtCoder · agc008_e

E. 下一个或下一个下一个

中文机器翻译题面 查看原题

分数: 1400 点

问题陈述

给你一个整数序列 a 长度 N。 有多少种排列 p 的整数 1 通过 N 满足以下条件?

  • 对于每个 1 ≤ i ≤ N,至少满足以下条件之一: p_i = a_i 和 p_{p_i} = a_i.

求计数模数 10^9 + 7.

约束

  • 1 ≤ N ≤ 10^5
  • a_i 是一个整数。
  • 1 ≤ a_i ≤ N

输入

输入由标准输入按以下格式给出:

N
a_1 a_2 ... a_N

输出

打印排列数 p 满足条件,取模 10^9 + 7.


示例输入 1

3
1 2 3

示例输出 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

2
1 1

示例输出 2

1

以下一种排列满足条件:

  • (2, 1)

示例输入 3

3
2 1 1

示例输出 3

2

以下两个排列满足条件:

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

示例输入 4

3
1 1 1

示例输出 4

0

示例输入 5

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

示例输出 5

6