Next or Nextnext

You are given an integer sequence a of length N. How many permutations p of the integers 1 through N satisfy the following condition?

• For each 1 ≤ i ≤ N, at least one of the following holds: p_i = a_i and p_{p_i} = a_i.

Find the count modulo 10^9 + 7.

Constraints

• 1 ≤ N ≤ 10^5
• a_i is an integer.
• 1 ≤ a_i ≤ N

Input

The input is given from Standard Input in the following format:

N a_1 a_2 ... a_N

Output

Print the number of the permutations p that satisfy the condition, modulo 10^9 + 7.

Examples

Input

3 1 2 3

Output

4

Input

2 1 1

Output

1

Input

3 2 1 1

Output

2

Input

3 1 1 1

Output

0

Input

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

Output

6

inputFormat

Input

The input is given from Standard Input in the following format:

N a_1 a_2 ... a_N

outputFormat

Output

Print the number of the permutations p that satisfy the condition, modulo 10^9 + 7.

Examples

Input

3 1 2 3

Output

4

Input

2 1 1

Output

1

Input

3 2 1 1

Output

2

Input

3 1 1 1

Output

0

Input

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

Output

6

样例

2
1 1

1