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>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#define MOD 1000000007

using namespace std;

typedef long long ll;

ll dp(int n,int m) {
  ll s1=1,s2=0;
  for(int i=1;i<=m;i++) {
  	ll f=(s1*(((n&1)&&n>1)?2LL:1LL)+s2*(i-1)%MOD*n)%MOD;
  	s2=s1;
  	s1=f;
  }
  return s1;
}

int a[100005],sum[100005];
bool vis[100005],cir[100005];
vector <int> son[100005];

int getlen(int x) {
  vis[x]=1;
  if (!cir[x]&&son[x].size()>=2) {
  	puts("0");
  	exit(0);
  }
  for(int i=0;i<son[x].size();i++)
    if (!cir[son[x][i]]) return getlen(son[x][i])+1;
  return 1;
}

int now[100005],l[100005],pos[100005];

ll calc(int x) {
  do {
  	vis[x]=1;
  	x=a[x];
  } while (!vis[x]);
  int d=0,tot=0;
  do {
  	cir[x]=1;
  	x=a[x];
  } while (!cir[x]);
  int t=x;
  do {
  	pos[x]=++d;
  	l[x]=getlen(x)-1;
  	if (l[x]) now[++tot]=x;
  	x=a[x];
  } while (x!=t);
  if (!tot) {
  	sum[d]++;
  	return 1;
  }
  ll ans=1;
  for(int i=1;i<=tot;i++) {
  	int p=now[i],q=now[i%tot+1];
  	int dis=(pos[q]-pos[p]+d)%d;
  	if (!dis) dis=d;
  	if (dis<l[q]) {
  		puts("0");
  		exit(0);
	  }
	if (dis>l[q]) ans=ans*2LL%MOD;
  }
  return ans;
}

int main() {
  int n;
  scanf("%d",&n);
  for(int i=1;i<=n;i++) {
  	scanf("%d",&a[i]);
  	son[a[i]].push_back(i);
  	if (son[a[i]].size()>2) {
  		puts("0");
  		exit(0);
	  }
  }
  ll ans=1;
  for(int i=1;i<=n;i++)
    if (!vis[i]) ans=(ans*calc(i))%MOD;
  for(int i=1;i<=n;i++)
    if (sum[i]) ans=ans*dp(i,sum[i])%MOD;
  printf("%lld\n",ans);
  return 0;
}