SUNGRAPH

#define task "SUNGRAPH"
#include <iostream>
#include <cstdio>

using namespace std;

using ll = long long;
using ld = long double;

constexpr int N = 1e6 + 5;
constexpr ll mod = 1e9 + 7;
int n, p[N];
ll f[N], ans(1), m;
int status[N], dep[N];

void Read()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        cin >> p[i];
}

ll Pow(ll a, ll b)
{
    ll ans = 1;
    for (; b; b >>= 1)
    {
        if (b & 1)
            ans = ans * a % mod;
        a = a * a % mod;
    }

    return ans;
}

void Solve()
{
    f[1] = 0;
    f[2] = 1ll * m * (m - 1) % mod;

    for (int i = 3; i <= n; ++i)
    {
        f[i] = (m * Pow(m - 1, i - 1) - f[i - 1]) % mod;
        (f[i] += mod) %= mod;
    }

    ans = 1;
    int cnt = 0;

    for (int i = 1; i <= n; ++i)
        if (!status[i])
        {
            int v = i;
            status[i] = i;
            dep[i] = 1;

            while (1)
            {
                if (status[p[v]] == 0)
                {
                    dep[p[v]] = dep[v] + 1;
                    status[p[v]] = i;
                    v = p[v];
                }
                else if (status[p[v]] == i)
                {
                    ans = ans * f[dep[v] - dep[p[v]] + 1] % mod;
                    cnt += dep[v] - dep[p[v]] + 1;

                    break;
                }
                else
                    break;
            }
        }

    cout << ans * Pow(m - 1, n - cnt) % mod;
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if (fopen(task ".INP", "r"))
    {
        freopen(task ".INP", "r", stdin);
        freopen(task ".OUT", "w", stdout);
    }

    Read();
    Solve();
}