#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rep2(i, s, n) for (ll i = s; i < (n); i++)

const ll MOD = 998244353;
ll modPow(ll a, ll n){
  if (n == 0) return 1;
  if (n == 1) return a % MOD;
  if (n % 2 == 1) return (a * modPow(a, n-1)) % MOD;
  ll t = modPow(a, n/2);
  return (t * t) % MOD;
}

int main(){
  ll n; cin >> n;
  vector<ll> f(n);
  rep(i, n){
    cin >> f[i];
    f[i]--;
  }
  ll num = 0;
  vector<bool> flag(n, false);
  rep(i, n){
    if (flag[i]) continue;
    multiset<ll> st;
    ll now = i;
    st.insert(now);
    rep(j, n){
      flag[now] = true;
      now = f[now];
      st.insert(now);
      if (flag[now]) break;
    }
    if (st.count(now) == 2) num++;
  }
  cout << modPow(2, num)-1 << endl;;
  
  return 0;
}
#include <bits/stdc++.h>
#include <cassert>
#define rep(i, N) for (int i = 0; i < (N); ++i)
#define rep2(i, a, b) for (ll i = a; i <= b; ++i)
#define rep3(i, a, b) for (ll i = a; i >= b; --i)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define nl '\n'
#define endl '\n'
#define all(c) begin(c), end(c)
#define ok() puts(ok ? "Yes" : "No");
#define pcnt(x) __builtin_popcountll(x)
#define df(x) ll x = in();
template <class T> bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T> bool chmin(T &a, const T &b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
using namespace std;
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using vvll = vector<vll>;
using ii = pair<int, int>;
using vvi = vector<vi>;
using vii = vector<ii>;
using vs = vector<string>;
using P = pair<ll, ll>;
using gt = greater<P>;
using minq = priority_queue<P, vector<P>, gt>;
using vP = vector<P>;
inline ll in() {
  ll x;
  scanf("%lld", &x);
  return x;
}
template <class T> void takeUnique(vector<T> &v) {
  auto last = std::unique(v.begin(), v.end());
  v.erase(last, v.end());
}
template <class T> void print(const initializer_list<T> &il) {
  for (auto x : il) {
    cout << x << " ";
  }
  cout << "\n";
}
inline void priv(vll a) {
  rep(i, (int)a.size() - 1) cout << a[i] << " ";
  cout << a.back() << nl;
}
inline void priv(vi a) {
  rep(i, (int)a.size() - 1) cout << a[i] << " ";
  cout << a.back() << nl;
}
const ll LINF = 8e18L + 1;
const int INF = 8e9 + 1;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
int dxx[] = {0, 1, 1, 1, 0, -1, -1, -1};
int dyy[] = {1, 1, 0, -1, -1, -1, 0, 1};
// g++ -std=c++17 -stdlib=libc++
#define _GLIBCXX_DEBUG
// This slows down the execution; even the time complexity, since it checks if
// std funcs such as lower_bound meets prereqs
int mod = 1e9 + 7;
int n, p;
ll f(ll nn) {
  if (nn == 0)
    return 1;
  ll ret = f(nn / 2);
  (ret *= ret) %= mod;
  if (nn & 1)
    (ret *= (p - 2)) %= mod;
  return ret;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout << fixed << setprecision(16);
  cin >> n >> p;
  ll ans = p - 1;
  ans *= f(n - 1);
  cout << ans % mod << nl;
  return 0;
}
