paleta

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9+7;
const int MN = 1e6+100;
ll ex(ll a, ll e) {
    ll res = 1;
    for(; e; e/=2) {
	if(e&1) {
	    res *= a;
	    res %= MOD;
	}
	a *= a;
	a %= MOD;
    }
    return res;
}
ll dp[MN];
vector<int> v[MN];
int par[MN];
bool used[MN];
int f(int x, vector<int> & v2) {
    used[x] = 1;
    if(used[par[x]]) {
	if(par[x] == x) {
	    v2.push_back(x);
	    return 0;
	}
	v2.push_back(par[x]);
	v2.push_back(x);
	return 1;
    }
    int q = f(par[x], v2);
    if(q == 0) {
	used[x] = 0;
	return 0;
    }
    if(x == v2[0]) {
	return 0;
    }
    v2.push_back(x);
    return 1;
}
int f2(int x) {
    used[x] = 1;
    ll ret = 1;
    for(auto y: v[x]) {
	if(!used[y]) {
	    ret += f2(y);
	}
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n,k;
    cin>>n>>k;
    dp[1] = k;
    dp[2] = k*(k-1)%MOD;
    dp[3] = k * (k-1)%MOD*(k-2)%MOD;
    for(int i = 4; i < MN; ++i) {
	dp[i] = (dp[i-2]*(k-1) + dp[i-1]*(k-2))%MOD;
    }
    ll ans = 1;
    int lol = 0;
    for(int i = 1; i <= n; ++i) {
	int x;
	cin>>x;
	par[i] = x;
	v[x].push_back(i);
	if(x == i) ++lol;
    }
    if(lol != n && k == 1) {
	cout<<0<<'\n';
	return 0;
    }
    for(int i = 1; i <= n; ++i) {
	if(!used[i]) {
	    vector<int> sykli;
	    f(i, sykli);
	    ans *= dp[sykli.size()];
	    ans %= MOD;
	    if(sykli.size() % 2 == 1 && k == 2) {
		cout<<0<<'\n';
		return 0;
	    }
	    //cout<<sykli.size()<<'\n';
	    //cout<<dp[sykli.size()]<<'\n';
	    for(auto y: sykli) {
		ll q = f2(y)-1;
		ans *= ex(k-1, q);
		ans %= MOD;
	    }
	}
    }
    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: WRONG ANSWER

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: WRONG ANSWER

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: ACCEPTED