PermutarePow

#include <bits/stdc++.h>

using namespace std;

ifstream fin ("permutarepow.in");
ofstream fout ("permutarepow.out");


const int NMAX = 1000000;

int fr[NMAX + 5] , ans[10001] , a , nans , n , b[10001] , nb , aa;

bool viz[NMAX + 5];

inline int Rest()
{
    int R = 0;
    for(int i = nans ; i >= 1 ; i--)
        R = (R * 10 + b[i]) % a;
    return R;
}

inline void CMMDC()
{
    int r , aux;
    while(a)
    {
        r = Rest();
        aux = a;
        nb = 0;
        while(aux)
        {
            b[++nb] = aux % 10;
            aux /= 10;
        }
        a = r;
    }
}

inline void INPARTIRE()
{
    int i , t = 0;
    for(i = nans ; i >= 1 ; i-- , t %= a)
        ans[i] = (t = t * 10 + ans[i]) / a;
    for(; nans > 1 && !ans[nans] ; --nans)
        ;
}

inline void INMULTIRE()
{
    int i , t = 0;
    for(i = 1 ; i <= nans || t ; i++ , t /= 10)
        ans[i] = (t += ans[i] * aa) % 10;
    nans = i - 1;
}

int main()
{
    int x , c , s;
    fin >> n;
    for(int i = 1 ; i <= n ; i++)
        fin >> x , fr[i] = x;
    for(int i = 1 ; i <= n ; i++)
        if(!viz[i] && i != fr[i])
    {
        c = fr[i];
        s = 1;
        viz[c] = true;
        while(c != i)
        {
            ++s;
            c = fr[c];
            viz[c] = true;
        }
        if(!nans)
        {
            while(s > 0)
            {
                ans[++nans] = s % 10;
                s /= 10;
            }
        }
        else
        {
            a = aa = s;
            nb = 0;
            for(int i = 1 ; i <= nans ; i++)
                b[++nb] = ans[i];

            CMMDC();
            a = 0;
            for(int i = 1 ; i <= nb ; i++)
                a = a * 10 + b[i];
            INPARTIRE();
            INMULTIRE();
        }
    }
    if(!nans)
    {
        nans = 1;
        ans[nans] = 1;

    }
    for(int i = nans ; i >= 1 ; i--)
        fout << ans[i];
    fout << "\n";
    fin.close();
    fout.close();
    return 0;
}