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:
//In the Name of God
//Ya Ali

#include<bits/stdc++.h>

#define int long long

#define pb push_back

#define err(A) cout<<#A<<" = "<<(A)<<endl

using namespace std;

const int M=1e9+7;
const int maxn=100100;

int n;

int a[maxn];

vector<int> g[maxn];

bool vis[maxn];

int cnt[maxn];

int dp[maxn];

int ans=1;

void gn()
{
  cout<<ans<<endl;
  exit(0);
}

int len(int v)
{
  int ret=1;
  int c=0;
  vis[v]=true;
  for(int u:g[v])
    if(!vis[u])
      {
	c++;
	ret+=len(u);
      }
  if(c>1)
    ans=0;
  return ret;
}

void solve(int v)
{
  vector<int> q,p;
  while(!vis[v])
    {
      vis[v]=true;
      q.pb(v);
      v=a[v];
    }
  for(int u:q)
    vis[u]=false;
  q.resize(0);
  while(!vis[v])
    {
      vis[v]=true;
      q.pb(v);
      v=a[v];
    }
  p.resize(q.size());
  int prv=-1;
  for(int i=0;i<q.size();i++)
    if(g[q[i]].size()==2)
      prv=i;
  if(prv==-1)
    {
      cnt[q.size()]++;
      return;
    }
  for(int i=0;i<q.size();i++)
    {
      p[i]=prv;
      if(g[q[i]].size()==2)
	{
	  int l1=len(q[i])-1;
	  int l2=(i-prv+q.size())%q.size();
	  if(l2==0) l2=q.size();
	  if(l1>l2)
	    ans=0;
	  if(l1<l2)
	    ans=ans*2%M;
	  prv=i;
	}
    }
}

int32_t main()
{
  ios::sync_with_stdio(0);cin.tie(0);
  
  cin>>n;

  for(int i=0;i<n;i++)
    cin>>a[i],a[i]--;
  
  for(int i=0;i<n;i++)
    g[a[i]].pb(i);

  for(int i=0;i<n;i++)
    if(g[i].size()>2)
      ans=0,gn();

  for(int i=0;i<n;i++)
    if(!vis[i])
      solve(i);
  
  for(int i=1;i<=n;i++)
    {
      dp[0]=1;  
      dp[1]=1+(i>2 and i&1);
      for(int j=2;j<=cnt[i];j++)
	dp[j]=(dp[j-1]*dp[1]+dp[j-2]*(j-1)*i)%M;
      ans=ans*dp[cnt[i]]%M;
    }
  
  gn();
  
  return 0;
}