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;
const int N=1e5+10;
const int mod=1e9+7;
int gi() {
    int x=0,o=1;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-') o=-1,ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*o;
}
int n,ans=1,a[N],du[N],pre[N],cnt[N],f[N];
bool vis[N];
int main() {
    cin>>n;
    for(int i=1;i<=n;i++) a[i]=gi(),du[a[i]]++;
    for(int i=1;i<=n;i++) {
        if(du[i]>2) return puts("0"),0;
        if(du[i]<2||vis[i]) continue;
        int p=i;
        do {
            if(vis[p]) return puts("0"),0;
            vis[p]=1;pre[a[p]]=p;p=a[p];
        } while(p!=i);
    }
    for(int i=1;i<=n;i++)
        if(!du[i]) {
            int p=i,l1=0,l2=0;
            while(!vis[p]) vis[p]=1,p=a[p],l1++;
            do l2++,p=pre[p]; while(du[p]!=2);
            if(l1<l2) ans=2ll*ans%mod;
            else if(l1>l2) return puts("0"),0;
        }
    for(int i=1;i<=n;i++)
        if(!vis[i]) {
            int p=i,l=0;
            do p=a[p],l++,vis[p]=1; while(p!=i);
            cnt[l]++;
        }
    for(int i=1;i<=n;i++) {
        int mul=1;if(i!=1&&(i&1)) mul++;
        f[0]=1;f[1]=mul;
        for(int j=2;j<=cnt[i];j++) f[j]=(1ll*f[j-2]*(j-1)%mod*i%mod+1ll*f[j-1]*mul%mod)%mod;
        ans=1ll*ans*f[cnt[i]]%mod;
    }
    printf("%d\n",ans);
    return 0;
}