F

#include <bits/stdc++.h>
using namespace std;
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
*/

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef map<int, int> mii;
typedef unordered_map<int, int> umii;
typedef map<ll, ll> mll;
typedef unordered_map<ll, ll> umll;
template <class T1, class T2>
void maximize(T1 &a, T2 b){
    if (b > a) a = b;
}
template <class T1, class T2>
void minimize(T1 &a, T2 b){
    if (b < a) a = b;
}
template <class T>
void read(T &number)
{
    bool negative = false;
    register int c;
    number = 0;
    c = getchar();
    while (c != '-' && !isalnum(c)) c = getchar();
    if (c=='-'){
        negative = true;
        c = getchar();
    }
    for (; (c>47 && c<58); c=getchar())
        number = number *10 + c - 48;
    if (negative)
        number *= -1;
}
template <class T, class ...Ts>
void read(T &a, Ts& ... args){
    read(a);
    read(args...);
}

/*
struct Node
{
    int node, len;
    Node() {node = len = 0;}
    Node(int node, int len) {this -> node = node, this -> len = len;}
};
typedef vector<Node> vg;
*/

#define MAX 1000001
#define MOD 998244353

#define fi first
#define se second
#define pf push_front
#define pb push_back

#define FOR(type, i, a, b) for(type i = (a); i <= (b); i++)
#define FORD(type, i, b, a) for(type i = (b); i >= (a); i--)

#define testBit(n, bit) ((n >> bit) & 1)
#define flipBit(n, bit) (n ^ (1ll << bit))
#define cntBit(n) __builtin_popcount(n)
#define cntBitll(n) __builtin_popcountll(n)
#define randomize mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());

struct Matrix{
    int mat[2][2];
    void clear(){
        memset(mat, false, sizeof(mat));
    }
    Matrix(){
        clear();
    }
    void unit(){
        mat[0][0] = mat[1][1] = 1;
    }
    int* operator [](int idx){return mat[idx];}
};
Matrix operator * (Matrix a, Matrix b){
    Matrix ans;
    FOR(int, k, 0, 1) FOR(int, i, 0, 1) FOR(int, j, 0, 1)
        ans[i][j] += 1ll * a[i][k] * b[k][j] % MOD,
        ans[i][j] %= MOD;
    return ans;
}

int theta, n, k;
int f[MAX];

const int BIT = 19;
Matrix mul[BIT + 1];
void init(){
    Matrix base;
    base[0][0] = 0, base[0][1] = k - 1, base[1][0] = 1, base[1][1] = k - 2;
    mul[0] = base;
    FOR(int, i, 1, BIT) mul[i] = mul[i - 1] * mul[i - 1];
}

int visited[MAX];
bool inLoop[MAX];
int root;
int dfs(int node, int x){
    // cerr << "dfs: " << node << ' ' << x << '\n';
    visited[node] = x;
    int jmp = f[node];

    if (visited[jmp]){
        if (visited[jmp] != x) return 0;
        inLoop[node] = true;
        if (jmp == node) return 1;
        root = jmp; return 1;
    }

    int answer = dfs(jmp, x);
    if (root){
        answer++; inLoop[node] = true;
        if (root == node) root = 0;
    }
    return answer;
}

int cal(int loopLen){
    if (loopLen == 1) return 1;
    Matrix ans; ans[0][0] = 1, ans[0][1] = 0;
    loopLen -= 1;
    for (int bit = 0; loopLen; bit++){
        if (loopLen & 1)
            ans = ans * mul[bit];
        loopLen >>= 1;
    }

    return ans[0][1];
}

main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifndef HIEU
    freopen("paleta.inp", "r", stdin);
    freopen("paleta.out", "w", stdout);
    #endif
    cin >> theta >> n >> k; init();
    FOR(int, i, 1, n) cin >> f[i];

    ll answer = 1, ptr = 1;
    FOR(int, i, 1, n)
        if (not visited[i]){
            // cerr << i << '\n';
            int loopSize = dfs(i, ptr++);
            if (loopSize == 0) continue;
            // cerr << loopSize << "out\n";
            // cerr << "root:" << root << '\n';
            answer *= 1ll * cal(loopSize) * k % MOD, answer %= MOD;
        }
    FOR(int, i, 1, n) if (not inLoop[i]) answer *= k - 1, answer %= MOD;
    cout << answer << '\n';
}