#include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #ifndef INCLUDED_MAIN #define INCLUDED_MAIN #include __FILE__ int main() { in(int, n); for (int i=0; i void debgp(T &x) { cerr << x; } template void debgp(pair &p) { cerr << "("; debgp(p.first); cerr << ", "; debgp(p.second); cerr << ")"; } template void debgp(vector &v) { cerr << "["; for (int i=0; i DEBUG_PRINT) cerr << " … ]\n"; } template void debgp(vector> &v) {cerr<<"[\n"; for (int i=0; i DEBUG_PRINT) cerr<<" ︙\n"; ; cerr << "]\n"; } #endif using i32 = int; using i64 = long long; const i64 INF = 0x0f0f'0f0f'0f0f'0f0f; template bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; } template bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } vector dx4 = {1, 0, -1, 0}; vector dy4 = {0, 1, 0, -1}; vector dx8 = {1, 1, 0, -1, -1, -1, 0, 1}; vector dy8 = {0, 1, 1, 1, 0, -1, -1, -1}; template istream& operator>>(istream&i,pair&v){ i>>v.first>>v.second; return i; } template istream& operator>>(istream&i,vector&v){ for(T&e : v) i>>e; return i; } template ostream& operator<<(ostream &o, pair &p){o<<"("< ostream& operator<<(ostream&o,vector&v){for(int i=0; i optional position(vector&v, T x) { auto it = std::find(v.begin(), v.end(), x); if (it == v.end()) return nullopt; return it - v.begin(); } optional position(string &v, char x) { auto it = std::find(v.begin(), v.end(), x); if (it == v.end()) return nullopt; return it - v.begin(); } template vector> run_length_encoding(vector&v) { vector> res; if (v.empty()) return res; res.emplace_back(v[0], 0); for (const auto& x : v) { if (res.back().first == x) { res.back().second++; } else { res.emplace_back(x, 1); } } return res; } struct init{init(){cin.tie(nullptr); ios::sync_with_stdio(false); cout<> name #define ll_in(name) long long name; cin >> name #define double_in(name) double name; cin >> name #define string_in(name) string name; cin >> name #define char_in(name) char name; cin >> name #define bool_in(name) bool name; cin >> name #define float_in(name) float name; cin >> name // コンテナ型のマクロ定義 #define vec_int_in(name, size) vector name(size); for(auto &x : name) cin >> x #define vec_ll_in(name, size) vector name(size); for(auto &x : name) cin >> x #define vec_double_in(name, size) vector name(size); for(auto &x : name) cin >> x #define vec_string_in(name, size) vector name(size); for(auto &x : name) cin >> x // ペア型のマクロ定義 #define pair_int_int_in(name) pair name; cin >> name.first >> name.second #define pair_ll_ll_in(name) pair name; cin >> name.first >> name.second // 2次元ベクトルのマクロ定義 #define vec2d_int_in(name, h, w) vector> name(h, vector(w)); for(int i=0; i> name[i][j] // 複数変数用マクロ #define in_1(t1, n1) t1##_in(n1) #define in_2(t1, n1, t2, n2) t1##_in(n1); t2##_in(n2) #define in_3(t1, n1, t2, n2, t3, n3) t1##_in(n1); t2##_in(n2); t3##_in(n3) #define in_4(t1, n1, t2, n2, t3, n3, t4, n4) t1##_in(n1); t2##_in(n2); t3##_in(n3); t4##_in(n4) // 可変長引数対応 (修正版) #define GET_MACRO(_1, _2, _3, _4, _5, _6, _7, _8, NAME, ...) NAME #define in(...) GET_MACRO(__VA_ARGS__, in_4, in_4, in_3, in_3, in_2, in_2, in_1, in_1)(__VA_ARGS__) // サイズ指定が必要なコンテナ用の特殊マクロ #define vec_in(type, name, size) vec_##type##_in(name, size) #define vec2d_in(type, name, h, w) vec2d_##type##_in(name, h, w) #define pair_in(t1, t2, name) pair_##t1##_##t2##_in(name) template class ModInt { private: long long val; public: ModInt():val(0) {} ModInt(long long x) : val((x % MOD + MOD) % MOD){} ModInt& operator+=(const ModInt& lhr) { val += lhr.val; if (val >= MOD) val -= MOD; return *this; } ModInt& operator-=(const ModInt& lhr) { val -= lhr.val; if (val < 0) val += MOD; return *this; } ModInt& operator*=(const ModInt& lhr) { val *= lhr.val % MOD; val %= MOD; return *this; } ModInt operator-() const { return ModInt(-val); } ModInt operator+(const ModInt& lhr) const { return ModInt(*this) += lhr; } ModInt operator-(const ModInt& lhr) const { return ModInt(*this) -= lhr; } ModInt operator*(const ModInt& lhr) const { return ModInt(*this) *= lhr; } bool operator==(const ModInt& lhr) const { return val == lhr.val; } bool operator!=(const ModInt& lhr) const { return val != lhr.val; } ModInt pow(long long x) const { ModInt res(1); ModInt v(*this); while (x > 0) { if (x & 1) res *= v; v *= v; x >>= 1; } return res; } friend std::ostream& operator<<(std::ostream& os, const ModInt& m) { return os << m.val; } }; using Mint = ModInt<998244353>; #include #include template class Matrix { private: std::vector> mat; public: Matrix() : mat(N, std::vector(M, T())) {} Matrix(const std::vector>& v) : mat(v) { if (v.size() != N || (v.size() > 0 && v[0].size() != M)) { throw std::invalid_argument("Input vector dimensions do not match matrix dimensions"); } } // 要素へのアクセス T& operator()(size_t i, size_t j) { return mat[i][j]; } const T& operator()(size_t i, size_t j) const { return mat[i][j]; } // 行列の加算 Matrix operator+(const Matrix& other) const { Matrix result; for (size_t i = 0; i < N; ++i) { for (size_t j = 0; j < M; ++j) { result(i, j) = mat[i][j] + other(i, j); } } return result; } // スカラー乗算 Matrix operator*(const T& scalar) const { Matrix result; for (size_t i = 0; i < N; ++i) { for (size_t j = 0; j < M; ++j) { result(i, j) = mat[i][j] * scalar; } } return result; } // 行列乗算 template Matrix operator*(const Matrix& other) const { Matrix result; for (size_t i = 0; i < N; ++i) { for (size_t j = 0; j < P; ++j) { for (size_t k = 0; k < M; ++k) { result(i, j) += mat[i][k] * other(k, j); } } } return result; } // 単位行列の生成 static Matrix identity() { Matrix result; for (size_t i = 0; i < N; ++i) { result(i, i) = T(1); } return result; } // 行列のべき乗 Matrix pow(long long exponent) const { if (exponent == 0) { return identity(); } if (exponent == 1) { return *this; } Matrix result = identity(); Matrix base = *this; while (exponent > 0) { if (exponent & 1) { result = result * base; } base = base * base; exponent >>= 1; } return result; } // 行列の表示(デバッグ用) void print() const { for (const auto& row : mat) { for (const auto& elem : row) { std::cout << elem << " "; } std::cout << std::endl; } } }; #endif