#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 40;
const ll mod = 998244353;

ll n, m;
struct mat {
	ll a[maxn][maxn];
	mat() {
		mems(a, 0);
	}
} F[maxn], G[maxn], H[maxn];

inline mat operator * (const mat &a, const mat &b) {
	mat res;
	for (int k = 0; k < maxn; ++k) {
		for (int i = 0; i < maxn; ++i) {
			for (int j = 0; j < maxn; ++j) {
				res.a[i][j] = (res.a[i][j] + a.a[i][k] * b.a[k][j]) % mod;
			}
		}
	}
	return res;
}

struct vec {
	ll a[maxn];
	vec() {
		mems(a, 0);
	}
};

inline vec operator * (const vec &a, const mat &b) {
	vec res;
	for (int i = 0; i < maxn; ++i) {
		for (int j = 0; j < maxn; ++j) {
			res.a[j] = (res.a[j] + a.a[i] * b.a[i][j]) % mod;
		}
	}
	return res;
}

void solve() {
	scanf("%lld%lld", &n, &m);
	for (int l = 0; l < 20; ++l) {
		for (int i = 0; i < 40; ++i) {
			F[l].a[i][i] = 1;
		}
		for (int i = 0; i <= l; ++i) {
			if (i < l) {
				F[l].a[i + 20][i + 20] = m;
			}
			for (int j = i; j < l; ++j) {
				F[l].a[j][i] = F[l].a[j + 20][i] = m * (((j - i) & 1) ? mod - 1 : 1) % mod;
			}
			F[l].a[l][i] = m * (((l - i) & 1) ? mod - 1 : 1) % mod;
		}
	}
	G[0] = H[0] = F[0];
	for (int i = 1; i < 20; ++i) {
		G[i] = H[i - 1] * F[i];
		H[i] = G[i] * H[i - 1];
	}
	vec ans;
	for (int i = 20; i < 40; ++i) {
		ans.a[i] = 1;
	}
	--n;
	for (int i = 19; ~i; --i) {
		if (n & (1 << i)) {
			ans = ans * G[i];
		}
	}
	printf("%lld\n", ans.a[0] * m % mod);
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}