#include <cstddef> #include <iostream> #include <set> #include <vector> using namespace std; using i64 = long long; template <int mod> struct Modular { int val; Modular() : val(0) { } Modular(i64 x) : val(x % mod) { if (val < 0) val += mod; } static Modular raw(int x) { if (x < 0) x += mod; else if (x >= mod) x -= mod; Modular res; res.val = x; return res; } friend Modular operator+(const Modular& lhs, const Modular& rhs) { return raw(lhs.val + rhs.val); } friend Modular operator*(const Modular& lhs, const Modular& rhs) { return i64(lhs.val) * rhs.val; } friend Modular& operator+=(Modular& lhs, const Modular& rhs) { return lhs = lhs + rhs; } friend Modular& operator*=(Modular& lhs, const Modular& rhs) { return lhs = lhs * rhs; } friend ostream& operator<<(ostream& os, const Modular& res) { return os << res.val; } }; using mint = Modular<998244353>; struct Matrix1D { int len; vector<mint> data; Matrix1D(int n) : len(n) , data(n) { } mint& operator[](int idx) { return data[idx]; } mint operator[](int idx) const { return data[idx]; } }; struct Matrix2D { int len; vector<vector<mint>> data; Matrix2D(int n) : len(n) , data(n, vector<mint>(n)) { } vector<mint>& operator[](int idx) { return data[idx]; } const vector<mint>& operator[](int idx) const { return data[idx]; } static Matrix2D id(int n) { Matrix2D res(n); for (int i = 0; i < n; ++i) res[i][i] = 1; return res; } // lhs * rhs friend Matrix2D operator*(const Matrix2D& lhs, const Matrix2D& rhs) { int n = lhs.len; Matrix2D res(n); for (int i = 0; i < n; ++i) { for (int k = 0; k < n; ++k) { mint cur = lhs[i][k]; for (int j = 0; j < n; ++j) res[i][j] += cur * rhs[k][j]; } } return res; } friend Matrix2D& operator*=(Matrix2D& lhs, const Matrix2D& rhs) { return lhs = lhs * rhs; } Matrix2D pow(size_t power) const { Matrix2D res = id(len), base = *this; for (; power > 0; power >>= 1, base *= base) { if (power & 1) res *= base; } return res; } }; Matrix1D operator*(const Matrix1D& lhs, const Matrix2D& rhs) { Matrix1D res(lhs.len); for (int i = 0; i < lhs.len; ++i) { mint cur = lhs[i]; for (int j = 0; j < rhs.len; ++j) res[j] += cur * rhs[i][j]; } return res; } inline unsigned rotate_left(unsigned val, unsigned width) { return (val >> 1) | ((val & 1) << (width - 1)); } inline unsigned rotate_right(unsigned val, unsigned width) { val <<= 1; val |= (val & (1U << width)) >> width; val &= (1U << width) - 1; return val; } inline bool is_independent_set(unsigned state, unsigned width) { return !(state & rotate_left(state, width)) && !(state & rotate_right(state, width)); } inline bool can_connect(unsigned upper, unsigned lower) { return !(upper & lower); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); size_t L; unsigned x; cin >> L >> x; unsigned cnt = 0; vector<unsigned> repr; vector<bool> vis(1U << x); vector<set<unsigned>> eq(1U << x); for (unsigned i = 0; i < 1U << x; ++i) { if (!is_independent_set(i, x) || vis[i]) continue; ++cnt; for (unsigned j = 0, cur = i; j < x; ++j, cur = rotate_left(cur, x)) { eq[i].insert(cur); vis[cur] = true; } if (*eq[i].begin() == i) repr.push_back(i); } if (L == 1) { cout << cnt << '\n'; return 0; } cnt = repr.size(); Matrix1D initial(cnt); Matrix2D transit(cnt); for (unsigned i = 0; i < cnt; ++i) { unsigned u = repr[i]; initial[i] = eq[u].size(); for (unsigned j = 0; j < cnt; ++j) { for (auto v : eq[repr[j]]) transit[i][j] += can_connect(u, v); } } auto res = initial * transit.pow(L - 1); mint ans; for (unsigned i = 0; i < cnt; ++i) ans += res[i]; cout << ans << '\n'; return 0; }