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<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int i=(a),_ed=(b);i<=_ed;++i)
#define DREP(i,a,b) for(int i=(a),_ed=(b);i>=_ed;--i)
#define mp(x,y) make_pair((x),(y))
#define sz(x) (int)(x).size()
#define pb push_back
typedef long long ll;
typedef pair<int,int> pii;
inline int read(){
    register int x=0,f=1;register char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=0;ch=getchar();}
    while(isdigit(ch)){x=x*10+(ch^'0');ch=getchar();}
    return f?x:-x;
}

const int N=1e5+5,mod=1e9+7;
int ans=1,n,a[N],d[N],vis[N],is[N],cnt[N],dis[N],f[N];

void work(int u){
    int len=0,s=-1,sd,las;
    while(is[u]){
	is[u]=0,++len;
	if(dis[u]){
	    if(!~s)s=len,sd=dis[u];
	    else ans=1ll*ans*((dis[u]<=len-las)+(dis[u]<len-las))%mod;
	    las=len;
	}
	u=a[u];
    }
    if(!~s)++cnt[len];
    else ans=1ll*ans*((sd<=s+len-las)+(sd<s+len-las))%mod;
}

int main(){
    //freopen("in.in","r",stdin);
    REP(i,1,n=read())a[i]=read(),++d[a[i]];
    REP(u,1,n){
	if(vis[u])continue;
	int p=u;while(!vis[p])vis[p]=u,p=a[p];
	if(vis[p]!=u)continue;
	while(!is[p])is[p]=1,p=a[p];
    }
    REP(i,1,n)if((is[i]&&d[i]>2)||(!is[i]&&d[i]>1))return puts("0"),0;
    REP(i,1,n)if(!d[i]){
	int p=i,l=0;
	while(!is[p])++l,p=a[p];
	dis[p]=l;
    }
    REP(i,1,n)if(is[i])work(i);
    REP(l,1,n){
	if(!cnt[l])continue;
	f[0]=1;
	REP(i,1,cnt[l]){
	    if(l>1&&l&1)f[i]=2ll*f[i-1]%mod;//i->p_i + i->p_{p_i}(同构)
	    else f[i]=f[i-1];//i->p_i
	    if(i>1)f[i]=(f[i]+1ll*f[i-2]*(i-1)%mod*l%mod)%mod;//i->p_{p_i}(变成2个环)
	}
	ans=1ll*ans*f[cnt[l]]%mod;
    }
    printf("%d\n",ans);
    return 0;
}
/*
 对于一个排列p_i,i向p_i连边,形成若干简单环(每个点入度出度都为1)
 a_i是p_i或p_{p_i},反映到现图上就是点i的下一个点或下下个点
 把p_i的边擦除,连i->a_i的边
 会有4中种情况,分别讨论一下
 现在就是给定a_i的图还原成p_i的图
 */