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 <cctype>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long int64;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
    while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
    while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
    return f*x;
}
const int N = 1e5+5, P = 1e9+7;
int n, a[N], d[N], rec[N], cir[N], size[N], c[N];
int64 ans = 1, f[N];
int main()
{
    n = read(); for(int i = 1; i <= n; ++i) a[i] = read(), ++d[a[i]];
    for(int i = 1, p; i <= n; ++i)
    {
        if(rec[i]) continue;
        p = i; while(!rec[p]) rec[p] = i, p = a[p];
        if(rec[p] == i) while(!cir[p]) cir[p] = 1, p = a[p];
    }
    for(int i = 1, k, p; i <= n; ++i) 
    {
        if((cir[i]&&d[i] > 2)||(!cir[i]&&d[i] > 1)) return puts("0"), 0;
        if(d[i]) continue; p = i, k = 0; 
        while(!cir[p]) ++k, p = a[p]; size[p] = k;
    }
    for(int i = 1, p, fir, j, k, firs; i <= n; ++i)
    {
        if(!cir[i]) continue;
        firs = fir = j = k = 0, p = i; 
        while(cir[p])
        {
            ++k, cir[p] = 0;
            if(size[p]&&!fir) j = fir = k, firs = size[p];
            else if(size[p]) ans = ans*((size[p] < k-j)+(size[p] <= k-j))%P, j = k;
            p = a[p];
        }
        if(!fir) ++c[k]; 
        else ans = ans*((firs < k-j+fir)+(firs <= k-j+fir))%P;
    }
    for(int i = 1; i <= n; ++i)
    {
        if(!c[i]) continue;
        f[0] = 1;
        for(int j = 1; j <= c[i]; ++j)
        {
            if(i > 1&&(i&1)) f[j] = (f[j-1]<<1)%P;
            else f[j] = f[j-1];
            if(j > 1) f[j] = (f[j]+f[j-2]*(j-1)%P*i%P)%P;
        }
        ans = ans*f[c[i]]%P;
    }
    printf("%lld\n", ans);
    return 0;
}
/* 
1
1 1
2
1 2 2
3
1 2 3 4
4
1 2 3 4 10
5
1 2 3 4 5 26
6
1 2 3 4 5 6 76
7
1 2 3 4 5 6 7 232
9
2 1 4 5 6 3 8 7 9
*/