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 <cstdio>
const int N=100005,mo=1000000007;
int deg[N],a[N],vis[N],b[N],cnt[N],f[N];
bool u[N];
int calc(int x,int y){return (x<y)+(x<=y);}
int main(){
	int n,ans=1;
	scanf("%d\n",&n);
	for (int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		deg[a[i]]++;
	}
	for (int i=1;i<=n;i++)
	if (!vis[i]){
		int j=i;
		for (;!vis[j];j=a[j]) vis[j]=i;
		if (vis[j]==i)
			for (;!u[j];j=a[j]) u[j]=1;
	}
	for (int i=1;i<=n;i++)
	if (!deg[i]){
		int j=i,k=0;
		for (;!u[j];j=a[j]) k++;
		b[j]=k;
	}
	else if (deg[i]>u[i]+1) ans=0;
	for (int i=1;i<=n && ans;i++)
	if (u[i]){
		int x=0,y=0,k=0;
		for (int j=i;u[j];j=a[j]){
			k++;u[j]=0;
			if (b[j]){
				if (!x) x=b[j],y=k;
					else ans=ans*calc(b[j],k)%mo;
				k=0;
			}
		}
		if (!x) cnt[k]++;
			else ans=ans*calc(x,y+k)%mo;
	}
	for (int i=1;i<=n && ans;i++){
		int x=(i&1)+(i>1);f[0]=1;
		for (int j=1;j<=cnt[i];j++){
			f[j]=f[j-1]*x%mo;
			if (j>1) f[j]=(f[j]+1ll*(j-1)*i%mo*f[j-2])%mo;
		}
		ans=1ll*ans*f[cnt[i]]%mo;
	}
	printf("%d\n",ans);
}