PALETA

#include<cstdio>
#include<stack>
#include<vector>

#define sc scanf
#define pr printf
#define fr first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
const int MN = 1000002;
const long long INF = 1000000007LL;

int n, k, f[MN], parent[MN], comp, ncomp[MN], ccomp[MN], pcomp[MN];
long long d[MN], power[MN], dtmp;
vector<int>g[MN];
bool u[MN];
stack< pair<int, int> >st;
pair<int, int>pa;
void dfs(int x, int p){
    int i;
    //pr("%d %d\n", x, p);
    st.push( mp(x, p) );
    while(!st.empty()){
        pa = st.top();
        st.pop();
        x = pa.fr;
        p = pa.se;
        //pr("%d\n", x);
        if(u[x]){
            if(ccomp[comp] == 0){
                ccomp[comp] = p;
                pcomp[comp] = x;
            }
        }
        else {
            u[x] = true;
            ncomp[comp]++;
            parent[x] = p;
            for(i=0; i<g[x].size(); i++){
                if(g[x][i] != parent[x]){
                    st.push( mp(g[x][i], x) );
                }
            }
        }
    }
}
int main(){
    freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
    sc("%d%d", &n, &k);
    int i, j, nc;
    d[3] = ( 1LL*k*(k-1)*(k-2) )%INF;
    dtmp = ( 1LL*k*(k-1) )%INF;
    for(i=4; i<=n; i++){
        d[i] = ( d[i-1]*(k-2) + dtmp*(k-1) )%INF;
        dtmp = d[i-1];
    }
    power[0] = 1;
    for(i=1; i<=n; i++){
        power[i] = ( power[i-1]*(k-1) )%INF;
    }

    for(i=1; i<=n; i++){
        sc("%d", &f[i]);
        if(f[i] != i && f[ f[i] ] != i){
            g[i].pb( f[i] );
            g[ f[i] ].pb(i);
        }
    }
    for(i=1; i<=n; i++){
        if(!u[i]){
            dfs(i, -1);
            comp++;
        }
    }
    long long ans = 1LL;
    for(i=0; i<comp; i++){
        if(ccomp[i] == 0){
            ans = ((( ans*power[ ncomp[i]-1 ] )%INF)*k)%INF;
        }
        else{
            nc = 0;
            for(j=ccomp[i]; j != parent[ pcomp[i] ]; j = parent[j]){
                //pr("ccomp -> %d\n", j);
                nc++;
            }
            //pr("%d\n", nc);
            ans = ((( ans*d[nc] )%INF)*power[ ncomp[i]-nc ])%INF;
        }
    }
    pr("%lld\n", ans);
    return 0;
}