#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
/*#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") //Optimization flags
#pragma GCC option("arch=native","tune=native","no-zero-upper") //Enable AVX
#pragma GCC target("avx2")  //Enable AVX*/

using namespace std;

using ll = long long;

#define mp make_pair

const int p = 1000000007;


int mul(int a, int b) {
    return (1LL * a * b) % p;
}

int add(int a, int b) {
    int s = (a+b);
    if (s>=p) s-=p;
    return s;
}

int sub(int a, int b) {
    int s = (a+p-b);
    if (s>=p) s-=p;
    return s;
}

int po(int a, int deg)
{
    if (deg==0) return 1;
    if (deg%2==1) return mul(a, po(a, deg-1));
    int t = po(a, deg/2);
    return mul(t, t);
}

int inv(int n)
{
    return po(n, p-2);
}

/*struct DSU {
    vector<int> sz;
    vector<int> parent;

    void make_set(int v) {
        parent[v] = v;
        sz[v] = 1;
    }

    int find_set(int v) {
        if (v == parent[v])
            return v;
        return parent[v] = find_set(parent[v]);
    }

    void union_sets(int a, int b) {
        a = find_set(a);
        b = find_set(b);
        if (a != b) {
            if (sz[a] < sz[b])
                swap(a, b);
            parent[b] = a;
            sz[a] += sz[b];
        }
    }

    DSU(int n) {
        sz.resize(n);
        parent.resize(n);
        for (int i = 0; i < n; i++) make_set(i);
    }
};*/

const int N = 1000000;

vector<int> facs(N), invfacs(N);

void init()
{
    facs[0] = 1;
    for (int i = 1; i<N; i++) facs[i] = mul(facs[i-1], i);
    invfacs[N-1] = inv(facs[N-1]);
    for (int i = N-2; i>=0; i--) invfacs[i] = mul(invfacs[i+1], i+1);
}

int C(int n, int k)
{
    return mul(facs[n], mul(invfacs[k], invfacs[n-k]));
}

vector<vector<int>> G;

int n;
vector<int> a;

vector<int> visited;

vector<vector<int>> cycles;

vector<int> len;

int dfs(int v, int par)
{
    //cout<<"entering dfs: "<<v<<' '<<par<<endl;
    int cnt = G[v].size();
    if (par!=-1) cnt--;
    if (cnt>1)
    {
        /*cout<<"broken: "<<v<<' '<<par<<endl;
        for (auto it: G[v]) cout<<it<<' ';
        cout<<endl;*/
        return -1;
    }
    if (cnt==0) return 0;
    for (auto it: G[v]) if (it!=par)
    {
        int res = dfs(it, -1);
        if (res!=-1) return res+1;
        else return -1;
    }
}

int solve(vector<int> a)
{
    int t = a.size();
    vector<int> cnt(t);
    for (int i = 0; i<t; i++)
    {
        cnt[i] = dfs(a[i], a[(i+t-1)%t]);
    }
    /*cout<<"counts:\n";
    for (int i = 0; i<t; i++) cout<<cnt[i]<<' ';
    cout<<endl;*/

    for (int i = 0; i<t; i++) if (cnt[i]==-1) return 0;



    int res = 1;
    int sum = 0;
    for (int i = 0; i<t; i++) sum+=cnt[i];
    if (sum==0) {len[t]++; return 1;}
    reverse(cnt.begin(), cnt.end());
    int cur = 0;
    while (cnt[cur]==0) cur++;
    int C = cur;
    while (true)
    {
        if (cnt[cur]>0)
        {
            int l = cnt[cur];
            bool dob = true;
            for (int i = 0; i<l; i++)
            {
                cur = (cur+1)%t;
                if (cnt[cur]>0)
                {
                    if (i<l-1) return 0;
                    if (i==l-1) dob = false;
                }
            }
            if (dob) res = mul(res, 2);
            if (cur==C) break;
        }
        else
        {
            cur = (cur+1)%t;
            if (cur==C) break;
        }
    }
    return res;

}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);

    init();



    cin>>n;
    a.resize(n);
    len.resize(n+1);
    G.resize(n);
    for (int i = 0; i<n; i++)
    {
        cin>>a[i]; a[i]--;
        G[a[i]].push_back(i);
    }

    /*for (int i = 0; i<n; i++) cout<<a[i]<<' ';
    cout<<endl;*/




    visited = vector<int>(n, -1);



    for (int i = 0; i<n; i++) if (visited[i]==-1)
    {
        //cout<<i<<":\n";
        visited[i] = i;
        int cur = a[i];
        while (visited[cur]==-1)
        {
            visited[cur] = i;
            cur = a[cur];
        }
        //cout<<"cur: "<<cur<<endl;
        if (visited[cur]!=i) continue;
        else
        {
            vector<int> cycle = {cur};
            int nxt = a[cur];
            while (nxt!=cur)
            {
                cycle.push_back(nxt);
                nxt = a[nxt];
            }
            cycles.push_back(cycle);
        }
    }
    /*for (auto it: cycles)
    {
        for (auto x: it) cout<<x<<' ';
        cout<<endl;
    }*/

    //cout<<"HERE"<<endl;
    int res = 1;

    //cout<<"HERE"<<endl;

    for (auto it: cycles)
    {
        /*for (auto x: it) cout<<x<<' ';
        cout<<endl;*/
        int answer = solve(it);
        //cout<<"answer: "<<answer<<endl;
        res = mul(res, answer);
    }

    for (int i = 1; i<=n; i++) if (len[i]!=0)
    {
        int x = len[i];
        //cout<<i<<": "<<x<<endl;
        int tot = 1;
        int F = 1;
        if (i%2 && i>1) tot = po(2, x);
        for (int prs = 1; prs<=x/2; prs++)
        {
            F = mul(F, mul(2*prs-1, i));
            int temp = mul(C(x, prs*2), F);
            if (i%2 && i>1) temp = mul(temp, po(2, x - 2*prs));
            tot = add(tot, temp);
        }
        //cout<<tot<<endl;
        res = mul(res, tot);
    }

    cout<<res;



}




Measured memory_bytes: 20788