#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
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();
    inline static vector<T> p{w}, ip{w.inv()};
    // primitives
    using vector<T>::vector; // inherit all constructors!
    F& resize(size_t sz) { return vector<T>::resize(__bit_ceil(sz)), *this; }
    F(size_t sz) : vector<T>(__bit_ceil(sz)) {}
    F slice(size_t sz) const {
        F f(begin(), begin() + min(sz = __bit_ceil(sz), size()));
        return f.resize(sz);
    }
    // NTT
    F& ntt(bool inv = false) { // inplace fft/ifft
        while (K >= p.size()) {
            p.push_back(p.back() * p.back());
            ip.push_back(ip.back() * ip.back());
        }
        for (int _ = 0; (1 << _) < size(); _++) {
            int s = inv ? 1 << _ : size() >> 1 >> _; // stride
            assert(s < (1 << K));
            int e = (1 << (K - 1)) / s;
            T dw = (inv ? ip : p)[__builtin_ctz(e)];
            for (int i = 0; i < size(); i += s << 1) {
                T W = 1;
                for (int j = 0; j < s; j++) {
                    T x = at(i | j), y = at(i | j | s);
                    tie(at(i | j), at(i | j | s)) = inv ?
                        make_tuple((x + y * W) * i2, (x - y * W) * i2) :
                        make_tuple(x + y, (x - y) * W);
                    W = W * dw;
                }
            }
        }
        return *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) { at(0) += v; return *this; }
    F operator+(int v) const { return F(*this) += v; }
    F& operator*=(const F &o) {
        int n = max(size(), o.size()) << 1;
        resize(n);
        F b = o.slice(n);
        ntt(), b.ntt();
        for (int i = 0; i < n; i++) at(i) *= b[i];
        return ntt(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.resize(k << 1).ntt();
            F h = slice(k).resize(k << 1).ntt();
            for (int i = 0; i < k << 1; i++) {
                g[i] *= mint<M>{2} - g[i] * h[i];
            }
            g.ntt(true).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;
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 f(n + 1), g(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);
    }
    F 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;
}