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>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;



#define SIZE 100005

ll N;
ll in_num[SIZE],in[SIZE][2];
ll POW[SIZE],fact[SIZE];
int table[SIZE],boss[SIZE],height[SIZE],member_num[SIZE];

//scc
vector<int> G[SIZE];
vector<int> reverse_G[SIZE];
stack<int> S;
int group_index;
int scc_NUM[SIZE];

bool check[SIZE];



ll extgcd(ll a,ll b,ll &x,ll &y){
	ll d = a;
	if(b != 0){
		d = extgcd(b,a%b,y,x);
		y -= (a/b)*x;
	}else{
		x = 1;
		y = 0;
	}
	return d;
}

ll mod_pow(ll x,ll count, ll mod){

	if(count == 0)return 1;
	ll ret = mod_pow((x*x)%mod,count/2,mod);
	if(count%2 == 1){

		ret = (ret*x)%mod;
	}
	return ret;
}


ll mod_inverse(ll a,ll m){
    ll x,y;
    extgcd(a,m,x,y);
    return (m+x%m)%m;
}

ll mod_fact(ll n,ll p,ll &e){
	e = 0;
	if(n == 0)return 1;

	int res = mod_fact(n/p,p,e);
	e += n/p;

	if(n/p%2 != 0)return res*(p-fact[n%p])%p;
	return res*fact[n%p]%p;
}


ll nCm(ll n,ll m,ll p){
   if(n < m) return 0;
   ll e1,e2,e3;
   ll a1 = mod_fact(n,p,e1),a2 = mod_fact(m,p,e2),a3 = mod_fact(n-m,p,e3);
   if(e1 > e2+e3)return 0;
   return a1 * mod_inverse(a2*a3%p,p)%p;
}


int get_boss(int id){
	if(boss[id] == id)return id; //自分が代表なら、自分の値を返す
	else{
		return boss[id] = get_boss(boss[id]); //代表でないなら、自分が所属する組織の代表を返しつつ、経路圧縮
	}
}

int is_same(int x,int y){
	return get_boss(x) == get_boss(y);
}

void unite(int x,int y){
	int boss_x = get_boss(x);
	int boss_y = get_boss(y);

	//既に同じグループなら何もしない
	if(boss_x == boss_y)return;

	//高さが高い方に吸収する
	if(height[boss_x] > height[boss_y]){

		member_num[boss_x] += member_num[boss_y];
		boss[boss_y] = boss_x;

	}else if(height[boss_x] < height[boss_y]){

		member_num[boss_y] += member_num[boss_x];
		boss[boss_x] = boss_y;

	}else{ //height[boss_x] == height[boss_y]

		member_num[boss_x] += member_num[boss_y];
		boss[boss_y] = boss_x;
		height[x]++;
	}
}

void init(){

	for(int i = 0; i < N; i++){
		boss[i] = i;
		height[i] = 0;
		member_num[i] = 1;
	}
}

void dfs(int node_id){
	check[node_id] = true;

	for(int i = 0; i < G[node_id].size(); i++){
		if(!check[G[node_id][i]])dfs(G[node_id][i]);
	}
	S.push(node_id);
}

void reverse_dfs(int node_id){
	check[node_id] = true;

	scc_NUM[group_index]++;

	for(int i = 0; i < reverse_G[node_id].size(); i++){
		if(!check[reverse_G[node_id][i]])reverse_dfs(reverse_G[node_id][i]);
	}
}


void func(){

	for(int i = 0; i < N; i++){

		in_num[i] = 0;
	}
	for(int i = 0; i < N; i++){
		G[i].clear();
		reverse_G[i].clear();
	}

	bool FLG = true;

	for(int i = 0; i < N; i++){

		scanf("%d",&table[i]);
		if(!FLG)continue;

		table[i]--;

		G[i].push_back(table[i]);
		reverse_G[table[i]].push_back(i);

		if(in_num[table[i]] <= 1){

			in[table[i]][in_num[table[i]]] = i;
			in_num[table[i]]++;

		}else{ //入次数3のノード発生

			FLG = false;
		}
	}
	if(!FLG){
		printf("0\n");
		return;
	}
	//入次数が2で、入次ノード以外のノードに出次しているノードがあったら不可
	for(int i = 0; i < N; i++){
		if(in_num[i] < 2)continue;

		if(table[i] != in[i][0] && table[i] != in[i][1]){

			printf("0\n");
			return;
		}
	}

	//閉路チェック
	for(int i = 0; i < N; i++){

		scc_NUM[i] = 0;
		check[i] = false;
	}

	//まずは帰りがけ順を計算
	for(int i = 0; i < N;i++){
		if(!check[i])dfs(i);
	}
	for(int i = 0; i < N;i++)check[i] = false;

	group_index = -1;
	//ノードを、帰りがけ順の逆順に、各強連結成分(グループ)に分解
	while(!S.empty()){
		if(!check[S.top()]){
			group_index++;

			reverse_dfs(S.top());
		}
		S.pop();
	}

	for(int i = 0; i <= group_index; i++){

		//要素数3以上の閉路
		if(scc_NUM[i] >= 3){

			printf("0\n");
			return;
		}
	}

	init();

	for(int i = 0; i < N; i++){

		unite(i,table[i]);
	}

	ll num_2 = 0,num_other = 0;

	for(int i = 0; i < N; i++){
		if(get_boss(i) == i){
			if(member_num[i] == 2){

				num_2++;

			}else{

				num_other++;
			}
		}
	}

	ll ans = 0;

	if(num_other == 0){

		ans = fact[num_2];
		ans *= POW[num_2];
		ans %= MOD;
		ans *= (num_2/2+1);
		ans %= MOD;

		printf("%lld\n",ans);

		return;
	}

	ll BASE = POW[num_2+num_other];

	BASE *= fact[num_2];
	BASE %= MOD;

	BASE *= fact[num_other];
	BASE %= MOD;

	ll A,B;

	for(ll i = 0; i <= num_2; i++){

		A = nCm(num_2+num_other-(i+2),num_2-i,MOD);
		A *= (num_2+num_other-i-1);
		A %= MOD;
		A *= (i/2+1);
		A %= MOD;
		A *= BASE;
		A %= MOD;

		ans += A;
		ans %= MOD;

		B = nCm(num_2+num_other-(i+1),num_2-i,MOD);
		B *= (i/2+1);
		B %= MOD;
		B *= 2;
		B %= MOD;
		B *= BASE;
		B %= MOD;

		ans += B;
		ans %= MOD;
	}
	printf("%lld\n",ans);
}

int main(){

	fact[0] = 1;
	for(ll i = 1; i < SIZE; i++){
		fact[i] = i*fact[i-1];
		fact[i] %= MOD;
	}

	POW[0] = 1;
	for(int i = 1; i < SIZE; i++){

		POW[i] = POW[i-1]*2;
		POW[i] %= MOD;
	}

	while(true){
		scanf("%lld",&N);
		if(N == 0)break;

		func();
	}

	return 0;
}