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>
#define pb push_back
#define mp make_pair
#define FL "a"
using namespace std;
typedef vector<int> VI;
typedef long long ll;
typedef double dd;
const int N=1e5+10;
const int mod=1e9+7;
inline ll read(){
  ll data=0,w=1;char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
  if(ch=='-')w=-1,ch=getchar();
  while(ch<='9'&&ch>='0')data=data*10+ch-48,ch=getchar();
  return data*w;
}
inline void file(){
  freopen(FL".in","r",stdin);
  freopen(FL".out","w",stdout);
}

inline void upd(int &a,int b){a+=b;if(a>=mod)a-=mod;}
inline void dec(int &a,int b){a-=b;if(a<0)a+=mod;}
inline int poww(int a,int b){
  int res=1;
  for(;b;b>>=1,a=1ll*a*a%mod)
    if(b&1)res=1ll*res*a%mod;
  return res;
}
inline void er(){puts("0");exit(0);}

int n,a[N],ans;
int d[N],head[N],nxt[N<<1],to[N<<1],cnt;
inline void add(int u,int v){to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;}
int t[N],f[N];

int vis[N],line[N],dis[N],cal[N],top,cir[N],len;
void dfs(int u){
  vis[u]=1;cal[++top]=u;
  for(int i=head[u],v;i;i=nxt[i])
    if(~i&1){
      if(!vis[v=to[i]])dfs(v);
      else
	for(int j=top;cal[j]!=v;j--)
	  cir[++len]=cal[j];
    }
  top--;
}

inline void solve(int x){
  top=len=0;
  for(int p=0;!vis[x];vis[x]=1,cal[++top]=x,p=x,x=a[x]);
  for(int i=top,k=1;i;i--){
    k?cir[++len]=cal[i],dis[cal[i]]=len:vis[cal[i]]=0;
    if(cal[i]==x)k=0;
  }  
  reverse(cir+1,cir+len+1);
  for(int i=1;i<=len;i++)dis[cir[i]]=len-dis[cir[i]]+1;
  //for(int i=1;i<=len;i++)printf("%d ",cir[i]);puts("");
  for(int k=1,u;k<=len;k++){
    u=cir[k];if(d[u]>2)er();line[u]=0;
    for(int i=head[u],v;i;i=nxt[i])
      if(!vis[v=to[i]]){
	line[u]++;vis[v]=1;
	for(v;d[v];v=to[head[v]],vis[v]=1,line[u]++)
	  if(d[v]>1)er();
      }
  }
  for(int k=1;!line[cir[k]];k++)
    if(k==len){t[len]++;return;}
  if(len==1&&line[cir[1]]<=1)return;
  top=0;
  for(int k=1;k<=len;k++)
    if(line[cir[k]])cal[++top]=cir[k];
  /*for(int i=1;i<=top;i++)
    printf("(%d,%d,%d)",cal[i],dis[cal[i]],line[cal[i]]);puts("");*/
  
  if(line[cal[1]]>dis[cal[1]]+(len-dis[cal[top]]))er();
  else ans=1ll*min(2,dis[cal[1]]+(len-dis[cal[top]])-line[cal[1]]+1)*ans%mod;
  
  for(int i=2;i<=top;i++)
    if(line[cal[i]]>dis[cal[i]]-dis[cal[i-1]])er();
    else ans=1ll*min(2,dis[cal[i]]-dis[cal[i-1]]-line[cal[i]]+1)*ans%mod;
}

int main()
{
  n=read();cnt=1;ans=1;
  for(int i=1;i<=n;i++){
    a[i]=read();d[a[i]]++;add(a[i],i);
    //printf("%d %d\n",i,a[i]);
    if(a[i]>n)er();
  }
  for(int i=1;i<=n;i++)
    if(!vis[i])solve(i);
  for(int i=1;i<=n;i++)
    if(t[i]){
      f[0]=1;
      for(int j=1;j<=t[i];j++){
	f[j]=1ll*((i&1)&&i!=1?2:1)*f[j-1]%mod;
	upd(f[j],1ll*(j-1)*i%mod*f[j-2]%mod);
      }
      ans=1ll*ans*f[t[i]]%mod;
    }
  printf("%d\n",ans);
  return 0;
}