Problem: Hey!

There is a new building with N + 1 rooms lined up in a row. Each room is a residence for one person, and all rooms are currently vacant, but N new people are scheduled to live here from next month. Therefore, when they start living, one room becomes vacant.

As a landlord, you want to propose many room allocations that suit their tastes. Here, the room allocation is a table that gives which room each person lives in. For example, when N = 3, "the first person is in room 4, the second person is in room 1, and the third person is in room 2".

Of course, it would be quick to propose all possible room allocations, but that would be meaningless, so some restrictions would be set in consideration of the time and effort of the landlord and the tastes of the residents.

First, after they start living in one of the proposed room allocations, they may be told, "I want to change to another proposed room allocation." The building is new and they know they prefer a new room with no one in it yet, so a different room allocation was suggested by simply moving one person to a vacant room. This can only happen if you can change it to. However, as a landlord, I want to avoid such troubles, so I would like to adjust the proposed room allocation so that such changes are not allowed. In other words, the proposed set of room allocations must satisfy the following. "For any two different proposed room allocations A and B, moving one person to a vacant room in room allocation A does not result in room allocation B."

Next, we know that each of the N people who will live in the future has exactly one preferred person. Therefore, all the proposed room allocations should be such that people who are preferable to all people live next to each other.

What is the maximum size of a set of room allocations that satisfy these conditions? Find the remainder divided by 1,000,000,007.

Input

The input consists of multiple datasets. Each dataset is represented in the following format.

> N
> a1 a2 ... aN
>

The first line of the dataset is given the integer N, which represents the number of people who will live in the building next month. This satisfies 2 ≤ N ≤ 100,000. The second line gives information on the number ai of the person who prefers to live in the next room for the i-th person. For this, 1 ≤ ai ≤ N and ai ≠ i are satisfied. Also, the number of datasets does not exceed 50. The end of the input is represented by a line consisting of only one zero.

> ### Output

For each data set, output the remainder of dividing the maximum number of room allocations that can be proposed at the same time by 1,000,000,007 in one line, as shown in the problem statement.

Sample Input


2
twenty one
3
3 1 2
Ten
2 1 1 1 1 1 1 1 1 1
8
2 1 4 3 3 7 6 6
twenty five
2 3 2 5 4 5 8 7 8 11 10 13 12 15 14 17 16 19 18 21 20 23 22 25 24
Ten
2 1 4 3 6 5 8 7 10 9
0



Output for Sample Input


2
0
0
144
633544712
11520





Example

Input

2
2 1
3
3 1 2
10
2 1 1 1 1 1 1 1 1 1
8
2 1 4 3 3 7 6 6
25
2 3 2 5 4 5 8 7 8 11 10 13 12 15 14 17 16 19 18 21 20 23 22 25 24
10
2 1 4 3 6 5 8 7 10 9
0


Output

2
0
0
144
633544712
11520

Solution (in CPP):

Solution:
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;



const int mod = 1000000007;
struct Mod {
public:
	int num;
	Mod() : Mod(0) { ; }
	Mod(long long int n) : num((n % mod + mod) % mod) {
		static_assert(mod<INT_MAX / 2, "mod is too big, please make num 'long long int' from 'int'");
	}
	Mod(int n) : Mod(static_cast<long long int>(n)) { ; }
	operator int() { return num; }
};

Mod operator+(const Mod a, const Mod b) { return Mod((a.num + b.num) % mod); }
Mod operator+(const long long int a, const Mod b) { return Mod(a) + b; }
Mod operator+(const Mod a, const long long int  b) { return b + a; }
Mod operator++(Mod &a) { return a + Mod(1); }
Mod operator-(const Mod a, const Mod b) { return Mod((mod + a.num - b.num) % mod); }
Mod operator-(const long long int a, const Mod b) { return Mod(a) - b; }
Mod operator--(Mod &a) { return a - Mod(1); }
Mod operator*(const Mod a, const Mod b) { return Mod(((long long)a.num * b.num) % mod); }
Mod operator*(const long long int a, const Mod b) { return Mod(a)*b; }
Mod operator*(const Mod a, const long long int b) { return Mod(b)*a; }
Mod operator*(const Mod a, const int b) { return Mod(b)*a; }
Mod operator+=(Mod &a, const Mod b) { return a = a + b; }
Mod operator+=(long long int &a, const Mod b) { return a = a + b; }
Mod operator-=(Mod &a, const Mod b) { return a = a - b; }
Mod operator-=(long long int &a, const Mod b) { return a = a - b; }
Mod operator*=(Mod &a, const Mod b) { return a = a * b; }
Mod operator*=(long long int &a, const Mod b) { return a = a * b; }
Mod operator*=(Mod& a, const long long int &b) { return a = a * b; }
Mod operator^(const Mod a, const int n) {
	if (n == 0) return Mod(1);
	Mod res = (a * a) ^ (n / 2);
	if (n % 2) res = res * a;
	return res;
}
Mod mod_pow(const Mod a, const long long  int n) {
	if (n == 0) return Mod(1);
	Mod res = mod_pow((a * a), (n / 2));
	if (n % 2) res = res * a;
	return res;
}

Mod inv(const Mod a) { return a ^ (mod - 2); }
Mod operator/(const Mod a, const Mod b) {
	assert(b.num != 0);
	return a * inv(b);
}
Mod operator/(const long long int a, const Mod b) {
	return Mod(a) / b;
}
Mod operator/=(Mod &a, const Mod b) {
	return a = a / b;
}

#define MAX_MOD_N 1024000

Mod fact[MAX_MOD_N], factinv[MAX_MOD_N];
void init(const int amax = MAX_MOD_N) {
	fact[0] = Mod(1); factinv[0] = 1;
	for (int i = 0; i < amax - 1; ++i) {
		fact[i + 1] = fact[i] * Mod(i + 1);
		factinv[i + 1] = factinv[i] / Mod(i + 1);
	}
}
Mod comb(const int a, const int b) {
	return fact[a] * factinv[b] * factinv[a - b];
}

int dfs(const vector<vector<int>>&rev_edges,const int now, vector<int>&used) {
	if(used[now])assert(false);
	used[now]=true;
	if (rev_edges[now].size() == 0) {
		return 1;
	}
	assert(rev_edges[now].size() == 1) ;{
		return 1+dfs(rev_edges,rev_edges[now][0],used);
	}
}

int main()
{
	init();
	while (true) {
		int N;cin>>N;
		if(!N)break;
		vector<int>edges;
		vector<vector<int>>rev_edges(N);
		for (int i = 0; i < N; ++i) {
			int a;cin>>a;
			edges.push_back(a-1);
			rev_edges[a-1].push_back(i);
		}
		bool ok=true;
		if(any_of(rev_edges.begin(), rev_edges.end(), [](const vector<int>&v) {return v.size() >= 3; }) ){
			ok=false;
		}
		Mod ans=0;
		if (ok) {
			vector<int>loves(N, -1);
			for (int i = 0; i < N; ++i) {
				if (i == edges[edges[i]]) {
					loves[i]=edges[i];
				}
			}
			for (int i = 0; i < N; ++i) {
				if (rev_edges[i].size() == 2 && loves[i] ==  -1) {
					ok=false;
				}
			}
			if (ok) {
				vector<int>used(N);
				vector<int>nums(N);
				for (int i = 0; i < N; ++i) {
					if (!used[i]) {
						if (loves[i]!=-1) {
							used[i] = true;
							if (rev_edges[i].size() == 1) {
								nums[i]=1;
							}
							else {
								for (auto e : rev_edges[i]) {
									if (e != edges[i]) {
										nums[i]=1+dfs(rev_edges,e,used);
									}
								}
							}
						}
					}
				}
				if (find_if(used.begin(), used.end(), [](const int a) {return a == false; }) != used.end()) {
					ok=false;
				}
				if (ok) {
					ans = 1;
					vector<int>v;
					for (int i = 0; i < N; ++i) {
						if (loves[i]!=-1) {
							if(i<edges[i])continue;
							int num = nums[i] + nums[edges[i]];
							v.push_back(num);
						}
					}

					const int two_num=count(v.begin(),v.end(),2);
					const int other_num=v.size()-two_num;

					ans=fact[other_num];
					ans*=mod_pow(2,two_num+other_num);

					ans*=fact[two_num];

					Mod kake=0;
					for (int t = 0; t <= two_num / 2; ++t) {
						const int rest=two_num-2*t;

						if(rest>other_num+1)continue;
						else {
							Mod plus=0;
							plus=comb(other_num+t,t);
							plus*=comb(other_num+1,rest);
							plus*=other_num+1+t;
							kake+=plus;
						}
					}
					ans*=kake;
				}
			}
			
		}
		cout<<ans<<endl;
		
	}
	return 0;
}