paleta

#include <iostream>
using namespace std;
int N, K;

const int M=1000000007;

int f[1222333];

int u[1222333];

int cli;
int cl[1222333];
int clz[1222333];

void gc(int c){
  if (cl[c]) return;
  cl[c]=cli;
  ++clz[cli];
  gc(f[c]);
}

void go(int c){
  if (u[c]==2) return;
  if (u[c]==1){
    ++cli;
    gc(c);
    return;
  }
  u[c]=1;
  go(f[c]);
  u[c]=2;
}


long long ksmp[1222333];
long long kerp[1222333];

int main(){  
  cin >> N >> K;
  ksmp[1]=K;
  kerp[1]=0;
  for (int i=2; i<1222333; ++i){
    ksmp[i]=kerp[i-1];
    kerp[i]=ksmp[i-1]*(K-1)%M+kerp[i-1]*(K-2)%M;
    kerp[i]%=M;
  }
  
  
  for (int i=0; i<N; ++i) cin >> f[i], --f[i];
  for (int i=0; i<N; ++i) go(i);
  long long ans=1;
  int cla=0;
  for (int i=1; i<=cli; ++i){cla+=clz[i];
    long long vrt;
    if (clz[i]==1) vrt=K;
    else vrt=ksmp[clz[i]-1]*(K-1)%M+kerp[clz[i]-1]*(K-2)%M;
    vrt%=M;
    ans*=vrt;
    ans%=M;
  }
  for (int j=0; j<N-cla; ++j) ans*=(K-1), ans%=M;
  cout << ans << "\n";
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: ACCEPTED