#include <cctype> // added for isdigit #include <cstddef> #include <functional> // added for std::plus/std::multiplies #include <initializer_list> #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(static_cast<int>(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 bool operator==(const Modular& lhs, const Modular& rhs) { return lhs.val == rhs.val; } 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 raw(lhs.val - rhs.val); } Modular operator-() const { return raw(mod - val); } friend Modular operator*(const Modular& lhs, const Modular& rhs) { return Modular(i64(lhs.val) * rhs.val); } Modular pow(long long power) const { Modular res = 1; Modular base = *this; while (power > 0) { if (power & 1) res *= base; base *= base; power >>= 1; } return res; } Modular inv() const { return pow(mod - 2); } friend Modular operator/(const Modular& lhs, const Modular& rhs) { return lhs * rhs.inv(); } 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 Modular& operator*=(Modular& lhs, const Modular& rhs) { return lhs = lhs * rhs; } friend Modular& operator/=(Modular& lhs, const Modular& rhs) { return lhs = lhs / rhs; } friend Modular operator~(const Modular& x) { return x.inv(); } // provide unary ~ as inverse (used originally) friend istream& operator>>(istream& is, Modular& res) { int ch = is.get(); int sign = 1; res = 0; while (ch != EOF && !isdigit(static_cast<unsigned char>(ch))) { if (ch == '-') sign = -sign; ch = is.get(); } if (ch == EOF) return is; res = ch - '0'; ch = is.get(); while (ch != EOF && isdigit(static_cast<unsigned char>(ch))) { res = res * 10 + (ch - '0'); ch = is.get(); } res *= sign; return is; } friend ostream& operator<<(ostream& os, const Modular& res) { return os << res.val; } }; using mint = Modular<998244353>; template <class T, class OuterOp = std::plus<T>, class InnerOp = std::multiplies<T>> struct Matrix { int row, col; OuterOp out_op; InnerOp in_op; vector<vector<T>> data; Matrix(int n = 0, int m = 0, T val = {}, const OuterOp& out = OuterOp(), const InnerOp& in = InnerOp()) : row(n) , col(m) , out_op(out) , in_op(in) , data(n, vector<T>(m, val)) { } Matrix(const vector<vector<T>>& mat, const OuterOp& out = OuterOp(), const InnerOp& in = InnerOp()) : row(mat.size()) , col(mat[0].size()) , out_op(out) , in_op(in) , data(mat) { } Matrix(const initializer_list<vector<T>>& mat, const OuterOp& out = OuterOp(), const InnerOp& in = InnerOp()) : row(mat.size()) , col(mat.begin()->size()) , out_op(out) , in_op(in) , data(mat) { } vector<T>& operator[](int idx) { return data[idx]; } const vector<T>& operator[](int idx) const { return data[idx]; } static Matrix id(int n) { Matrix res(n, n); for (int i = 0; i < n; ++i) res[i][i] = 1; return res; } friend bool operator==(const Matrix& lhs, const Matrix& rhs) { return lhs.data == rhs.data; } // lhs * rhs friend Matrix operator*(const Matrix& lhs, const Matrix& rhs) { Matrix res(lhs.row, rhs.col); for (int i = 0; i < lhs.row; ++i) { for (int k = 0; k < lhs.col; ++k) { T cur = lhs[i][k]; for (int j = 0; j < rhs.col; ++j) res[i][j] = lhs.out_op(res[i][j], lhs.in_op(cur, rhs[k][j])); } } return res; } // lhs + rhs friend Matrix operator+(Matrix lhs, const Matrix& rhs) { for (int i = 0; i < lhs.row; ++i) { for (int j = 0; j < lhs.col; ++j) lhs[i][j] = lhs.out_op(lhs[i][j], rhs[i][j]); } return lhs; } friend Matrix& operator+=(Matrix& lhs, const Matrix& rhs) { for (int i = 0; i < lhs.row; ++i) { for (int j = 0; j < lhs.col; ++j) lhs[i][j] = lhs.out_op(lhs[i][j], rhs[i][j]); } return lhs; } friend Matrix& operator*=(Matrix& lhs, const Matrix& rhs) { return lhs = lhs * rhs; } Matrix pow(size_t power) const { Matrix res = id(row), base = *this; for (; power > 0; power >>= 1, base *= base) { if (power & 1) res *= base; } 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<set<unsigned>> eq(1U << x); for (unsigned i = 0; i < 1U << x; ++i) { if (!is_independent_set(i, x)) continue; ++cnt; for (unsigned j = 0, cur = i; j < x; ++j, cur = rotate_left(cur, x)) eq[i].insert(cur); if (*eq[i].begin() == i) repr.push_back(i); } if (L == 1) { cout << (x == 1 ? 2 : cnt) << '\n'; return 0; } cnt = repr.size(); Matrix<mint> transit(cnt, cnt), initial(1, cnt); for (unsigned i = 0; i < cnt; ++i) { unsigned u = repr[i]; initial[0][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[0][i]; cout << ans << '\n'; return 0; }