Problem: 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

Solution (in CPP):

Solution:
#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;

typedef long long i64;
class no_solution: public std::exception
{
public:
	no_solution()
	{
	}

	const char * what() const noexcept
	{
		return "no solution under such constrains";
	}
};

const int MAXN = 100000 + 5;
const int MOD = 1e9 + 7;

int N;
i64 answer, dp[MAXN];
int degree[MAXN], lenCnt[MAXN];
int pre[MAXN], nxt[MAXN];
bool vis[MAXN];

void findCycle()
{
	for (int i = 1; i <= N; i++)
	{
		if (degree[i] > 2)
			throw no_solution();
		if (degree[i] != 2 || vis[i])
			continue;

		int cur = i;

		do
		{
			if (vis[cur])
				throw no_solution();
			vis[cur] = true;
			pre[nxt[cur]] = cur;
			cur = nxt[cur];
		} while (cur != i);
	}
}

void processCircleBasedTree()
{
	for(int i = 1; i <= N; i++)
	{
		if(degree[i])
			continue;

		int cur = i, footLen = 0, cycleLen = 0;

		while(!vis[cur])
		{
			vis[cur] = true;
			cur = nxt[cur];
			footLen++;
		}

		do
		{
			cur = pre[cur];
			cycleLen++;
		}while(degree[cur] == 1);

		if(footLen < cycleLen)
			answer = answer * 2 % MOD;
		if(footLen > cycleLen)
			throw no_solution();
	}
}

void countCycle()
{
	for(int i = 1; i <= N; i++)
	{
		if(vis[i])
			continue;

		int cur = i, len = 0;

		do
		{
			vis[cur] = true;
			cur = nxt[cur];
			len++;
		}while(cur != i);

		lenCnt[len]++;
	}
}

int main()
{
	answer = 1;
	ios::sync_with_stdio(false), cin.tie(nullptr);
	cin >> N;

	for (int i = 1; i <= N; i++)
		cin >> nxt[i], degree[nxt[i]]++;

	try
	{
		findCycle();
		processCircleBasedTree();
		countCycle();

		for(int i = 1; i <= N; i++)
		{
			dp[0] = 1LL;
			for(int j = 1; j <= lenCnt[i]; j++)
			{
				dp[j] = dp[j-1] * (((i % 2 == 0) || i == 1) ? 1 : 2);
				if(j >= 2)
					dp[j] = (dp[j] + ((((dp[j-2] * (j-1)) % MOD) * i) % MOD)) % MOD;
			}

			answer = answer * dp[lenCnt[i]] % MOD;
		}

		cout << answer << endl ;
	} catch (const std::exception & x)
	{
		cout << "0" << endl;
		cerr << x.what() << endl;
	}
}