#include <bits/stdc++.h>
using namespace std;
using namespace std;
using namespace std;
using ll = long long;
template <int M>
struct mint {
    ll v = 0;
    mint() {}
    mint(ll v) { this->v = (v % M + M) % M; }
    mint operator+(const mint &o) const { return v + o.v; }
    mint& operator+=(const mint& o) { v = (v + o.v) % M; return *this; }
    mint operator*(const mint &o) const { return v * o.v; }
    mint& operator*=(const mint& o) { v = (v * o.v) % M; return *this; }
    mint operator-() const { return mint{0} - *this; }
    mint operator-(const mint &o) const { return v - o.v; }
    mint& operator-=(const mint& o) { mint t = v - o.v; v = t.v; return *this; }
    mint exp(int y) const { mint r = 1, x = v; for (y <<= 1; y >>= 1; x = x * x) if (y & 1) r = r * x; return r; }
    mint operator/(mint o) { return *this * o.inv(); }
    mint inv() const { assert(v); return exp(M - 2); }
    friend istream& operator>>(istream& s, mint& v) { s >> v.v; return s; }
    friend ostream& operator<<(ostream& s, const mint& v) { s << v.v; return s; }
};
const int M = 998244353;
const int K = 23; // largest power of 2 that divides M - 1
// polynomial
using T = mint<M>;
struct F : vector<T> {
    inline static T w = mint<M>{3}.exp((M - 1) / (1 << K));
    inline static T i2 = mint<M>{2}.inv();
    // primitives
    F& resize(size_t sz) { return vector<T>::resize(__bit_ceil(sz)), *this; }
    F slice(size_t sz) const {
        F g; g.resize(sz);
        for (int i = 0; i < min(size(), g.size()); i++) g[i] = at(i);
        return g;
    }
    F(initializer_list<T> l = {}) : vector<T>(l) {}
    F(int n) : vector<T>(1, n) {}
    bool f = false; // whether in fft state
    // FFT
    F& fft(bool inv = false) { // inplace fft/ifft
        if (f == inv) for (int _ = 0; (1 << _) < size(); _++) {
            int s = inv ? 1 << _ : size() >> 1 >> _; // stride
            assert(s < (1 << K));
            T dw = w.exp((1 << (K - 1)) / s);
            if (inv) dw = dw.inv();
            T W = 1;
            for (int i = 0; i < size(); i++) if (!(i & s)) {
                W = (i & (s - 1) ? W * dw : 1);
                T x = at(i), y = at(i | s);
                tie(at(i), at(i | s)) = inv ?
                    make_tuple((x + y * W) * i2, (x - y * W) * i2) :
                    make_tuple(x + y, (x - y) * W);
            }
        }
        return f = !inv, *this;
    }
    //
    // cout override
    friend ostream& operator<<(ostream& os, F f) {
        for (mint<M> x : f) os << x << " ";
        return os;
    }
    // operations
    F& operator+=(const F &o) {
        for (int i = 0; i < min(size(), o.size()); i++) at(i) += o.at(i);
        return *this;
    }
    F operator+(const F &o) const { return F(*this) += o; }
    F& operator+=(int v) { if (f) for (T &x : *this) x += v; else at(0) += v; return *this; }
    F operator+(int v) const { return F(*this) += v; }
    F operator*=(const F &o) {
        int n = 2 * max(size(), o.size());
        resize(n);
        F b = o.slice(n);
        fft(), b.fft();
        for (int i = 0; i < n; i++) at(i) *= b[i];
        return fft(true);
    }
    F& operator*=(int v) { for (T &x : *this) x *= v; return *this; }
    F operator*(int v) const { return F(*this) *= v; }
    F operator*(const F &o) const { return F(*this) *= o; }
    F operator/=(const F &o) { return *this *= o.inv(); }
    F operator/(const F &o) const { return F(*this) /= o; }
    // inverse
    F inv() const {
        if (!at(0).v) throw logic_error("cannot invert polynomial with f(0) == 0");
        F g{at(0).inv()};
        for (int k = 2; k <= size(); k <<= 1) {
            g *= ((slice(k) * g).resize(k) * -1 + 2);
            g.resize(k);
        }
        return g;
    }
};
using ll = long long;
const ll inf = 1e18;
using namespace std;
template <int A, int M>
struct Combo {
  mint<M> F[A], F_i[A];
  Combo() { F[0] = F_i[0] = 1; for (int i = 1; i < A; i++) F_i[i] = (F[i] = F[i - 1] * i).inv(); }
  mint<M> C(int n, int k) { return n < k ? 0 : F[n] * F_i[n - k] * F_i[k]; }
};
const int N = 6e6 + 1;
F f, g, gf;
Combo<N, M> C;
mint<M> ctln(int n) { return C.C(2 * n, n) / (n + 1); }
int c[N];
int main() {
    int n; mint<M> k; cin >> n >> k;
    f.resize(n + 1), g.resize(n + 1);
    g[1] = k;
    // gcd has to be either 2 * n or <= n
    for (int i = 1; 2 * i <= n; i++) {
        f[2 * i] = ctln(i - 1) * k * (k - 1).exp(i - 1);
        g[i * 2 + 1] = C.C(2 * i, i) * k * (k - 1).exp(i);
    }
    gf = (f / (f * -1 + 1) + 1).slice(n) * (g + 1); // [i] -> # of colorings for RBS + extra stuff of len i
    for (int i = 1; i <= 2 * n; i++) ++c[gcd(i, 2 * n)];
    for (int i = 1; i <= n; i++) gf[2 * n] += mint<M>{i} / (2 * n - i) * C.C(2 * n - i, n) * (k - 1).exp(n - i) * k.exp(i);
    mint<M> r = 0;
    for (int i = 1; i <= 2 * n; i++) {
        r += gf[i] * c[i];
    }
    cout << r / (2 * n) << endl;
}