#ifdef NACHIA #define _GLIBCXX_DEBUG #else #define NDEBUG #endif #include #include #include #include #include #include #include #include #include using i64 = long long; using u64 = unsigned long long; #define rep(i,n) for(int i=0; i=0; i--) const i64 INF = 1001001001001001001; const char* yn(bool x){ return x ? "Yes" : "No"; } template void chmin(A& l, const A& r){ if(r < l) l = r; } template void chmax(A& l, const A& r){ if(l < r) l = r; } template using nega_queue = std::priority_queue,std::greater>; using Modint = atcoder::static_modint<998244353>; //#include "nachia/vec.hpp" using namespace std; // (edited) Nyaan's library namespace nachia{ // output : denominator of rational gf template std::vector BerlekampMassey(const std::vector &s){ const int N = (int)s.size(); std::vector b, c; b.reserve(N+1); c.reserve(N+1); const Modint Zero = Modint(0); const Modint One = Modint(1); b.push_back(One); c.push_back(One); Modint y = One; for(int ed=1; ed<=N; ed++){ int l = int(c.size()); int m = int(b.size()); Modint x = Zero; for(int i=0; i #include namespace nachia{ // ax + by = gcd(a,b) // return ( x, - ) std::pair ExtGcd(long long a, long long b){ long long x = 1, y = 0; while(b){ long long u = a / b; std::swap(a-=b*u, b); std::swap(x-=y*u, y); } return std::make_pair(x, a); } } // namespace nachia namespace nachia{ class DynamicModSupplier{ using u64 = unsigned long long; using Int = unsigned int; private: u64 imod; Int mod; // atcoder library u64 reduce2(u64 z) const noexcept { // atcoder library #ifdef _MSC_VER u64 x; _umul128(z, im, &x); #else using u128 = unsigned __int128; u64 x = (u64)(((u128)(z)*imod) >> 64); #endif return z - x * mod; } Int reduce(u64 z) const noexcept { Int v = reduce2(z); if(mod <= v) v += mod; return v; } public: DynamicModSupplier(unsigned int MOD = 998244353) : mod(MOD) { assert(2 <= MOD); assert(MOD < (1u << 31)); imod = (u64)(-1) / mod + 1; } Int add(Int a, Int b) const { a += b; if(a >= mod){ a -= mod; } return a; } Int sub(Int a, Int b) const { a -= b; if(a >= mod){ a += mod; } return a; } Int mul(Int a, Int b) const { return reduce((u64)a * b); } Int muladd(Int a, Int b, Int c) const { return reduce((u64)a * b + c); } Int inv(Int a) const { Int v = ExtGcd(a, mod).first; return (v < mod) ? v : (v + mod); } Int pow(Int a, u64 i) const { Int r = a, ans = 1; while(i){ if(i & 1) ans = mul(ans, r); i /= 2; r = mul(r, r); } return ans; } Int getMod() const { return mod; } }; } // namespace nachia namespace nachia{ template struct GarnerMod{ using Int = unsigned int; using IntLong = unsigned long long; std::vector mods; std::vector dynmods; std::vector> table_coeff; std::vector table_coeffinv; void precalc(std::vector new_mods){ mods = std::move(new_mods); dynmods.resize(mods.size()); for(size_t i=0; i(nmods, 1)); for(int j=0; j& x){ int nmods = mods.size(); std::vector table_const(nmods); FinishType res = 0; FinishType res_coeff = 1; for(int j=0; j calc(std::vector> x){ int n = x[0].size(), m = x.size(); std::vector res(n); std::vector buf(m); for(int i=0; i std::vector PartConvolution(std::vector A, std::vector B) { std::vector> AA(A.size()); for(std::size_t i=0; i> BB(B.size()); for(std::size_t i=0; i res(AB.size()); for(std::size_t i=0; i std::vector Convolution(std::vector A, std::vector B){ auto Q1 = PartConvolution(A, B); auto Q2 = PartConvolution(A, B); auto Q3 = PartConvolution(A, B); GarnerMod garner; garner.precalc({ 998244353, 897581057, 880803841 }); return garner.calc({ Q1, Q2, Q3 }); } } // namespace nachia namespace nachia{ template Modint KthTermOfRationalGF( std::vector denom, std::vector numer, unsigned long long K ){ assert(denom.size() != 0); assert(denom.size() == numer.size()); assert(denom[0].val() != 0); int n = (int)denom.size(); while(K != 0){ auto Qn = denom; Qn.push_back(Modint(0)); for(int i=1; i Modint KthTermOfLinearRecurrence( std::vector denom, std::vector firstTerms, unsigned long long K ){ assert(denom.size() <= firstTerms.size()); firstTerms.resize(denom.size()); auto numer = Convolution(firstTerms, denom); numer.resize(denom.size()); return KthTermOfRationalGF(std::move(denom), std::move(numer), K); } } // namespace nachia namespace nachia{ template class Comb{ private: std::vector F; std::vector iF; public: void extend(int newN){ int prevN = (int)F.size() - 1; if(prevN >= newN) return; F.resize(newN+1); iF.resize(newN+1); for(int i=prevN+1; i<=newN; i++) F[i] = F[i-1] * Modint::raw(i); iF[newN] = F[newN].inv(); for(int i=newN; i>prevN; i--) iF[i-1] = iF[i] * Modint::raw(i); } Comb(int n = 1){ F.assign(2, Modint(1)); iF.assign(2, Modint(1)); extend(n); } Modint factorial(int n) const { return F[n]; } Modint invFactorial(int n) const { return iF[n]; } Modint invOf(int n) const { return iF[n] * F[n-1]; } Modint comb(int n, int r) const { if(n < 0 || n < r || r < 0) return Modint(0); return F[n] * iF[r] * iF[n-r]; } Modint invComb(int n, int r) const { if(n < 0 || n < r || r < 0) return Modint(0); return iF[n] * F[r] * F[n-r]; } Modint perm(int n, int r) const { if(n < 0 || n < r || r < 0) return Modint(0); return F[n] * iF[n-r]; } Modint invPerm(int n, int r) const { if(n < 0 || n < r || r < 0) return Modint(0); return iF[n] * F[n-r]; } Modint operator()(int n, int r) const { return comb(n,r); } }; } // namespace nachia void testcase(){ int N,M,K; cin >> N >> M >> K; if(M == 1){ cout << Modint(2).pow(N).val() << '\n'; return; } auto comb = nachia::Comb(N); int Z = (N+1)*2+1; vector A(Z); { vector dp(N+1); dp[N] = 1; rep(z,Z){ vector nx(N+1); rep(i,N+1) rep(j,i+1) if(K<=j) rep(k,N-i+1){ nx[j+k] += comb(i,j) * comb(N-i,k) * dp[i]; } swap(dp, nx); rep(i,N+1) A[z] += dp[i]; } } auto rec = nachia::BerlekampMassey(A); auto ans = nachia::KthTermOfLinearRecurrence(rec, A, M-1); cout << ans.val() << '\n'; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); #ifdef NACHIA int T; cin >> T; for(int t=0; t