#line 1 "c.cpp" #include using namespace std; using ll=long long; const ll ILL=2167167167167167167; const int INF=2100000000; #define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++) #define all(p) p.begin(),p.end() template using _pq = priority_queue, greater>; template int LB(vector &v,T a){return lower_bound(v.begin(),v.end(),a)-v.begin();} template int UB(vector &v,T a){return upper_bound(v.begin(),v.end(),a)-v.begin();} template bool chmin(T &a,T b){if(b bool chmax(T &a,T b){if(a void So(vector &v) {sort(v.begin(),v.end());} template void Sore(vector &v) {sort(v.begin(),v.end(),[](T x,T y){return x>y;});} bool yneos(bool a,bool upp=false){if(a){cout<<(upp?"YES\n":"Yes\n");}else{cout<<(upp?"NO\n":"No\n");}return a;} template void vec_out(vector &p,int ty=0){ if(ty==2){cout<<'{';for(int i=0;i<(int)p.size();i++){if(i){cout<<",";}cout<<'"'< T vec_min(vector &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmin(ans,x);return ans;} template T vec_max(vector &a){assert(!a.empty());T ans=a[0];for(auto &x:a) chmax(ans,x);return ans;} template T vec_sum(vector &a){T ans=T(0);for(auto &x:a) ans+=x;return ans;} int pop_count(long long a){int res=0;while(a){res+=(a&1),a>>=1;}return res;} template T square(T a){return a * a;} #line 3 "/Users/Shared/po167_library/fps/FPS_Boston_Mori.hpp" #include #line 4 "/Users/Shared/po167_library/fps/FPS_extend.hpp" namespace po167{ // in : DFT(v) (len(v) = z) // out : DFT(v) (len(v) = 2 * z) template void FPS_extend(std::vector &v){ int z = v.size(); T e = (T(atcoder::internal::primitive_root_constexpr(T::mod()))).pow(T::mod() / (2 * z)); auto cp = v; atcoder::internal::butterfly_inv(cp); T tmp = (T)(1) / (T)(z); for (int i = 0; i < z; i++){ cp[i] *= tmp; tmp *= e; } atcoder::internal::butterfly(cp); for (int i = 0; i < z; i++) v.push_back(cp[i]); }; } #line 3 "/Users/Shared/po167_library/fps/FPS_pick_even_odd.hpp" namespace po167{ // s.t |v| = 2 ^ s (no assert) template void FPS_pick_even_odd(std::vector &v, int odd){ int z = v.size() / 2; T half = (T)(1) / (T)(2); if (odd == 0){ for (int i = 0; i < z; i++){ v[i] = (v[i * 2] + v[i * 2 + 1]) * half; } v.resize(z); } else { T e = (T(atcoder::internal::primitive_root_constexpr(T::mod()))).pow(T::mod() / (2 * z)); T ie = T(1) / e; std::vector es = {half}; while ((int)es.size() != z){ std::vector n_es((int)es.size() * 2); for (int i = 0; i < (int)es.size(); i++){ n_es[i * 2] = (es[i]); n_es[i * 2 + 1] = (es[i] * ie); } ie *= ie; std::swap(n_es, es); } for (int i = 0; i < z; i ++){ v[i] = (v[i * 2] - v[i * 2 + 1]) * es[i]; } v.resize(z); } } } #line 7 "/Users/Shared/po167_library/fps/FPS_Boston_Mori.hpp" namespace po167{ // return [x^k] P(x) / Q(x) template T Boston_Mori(long long k, std::vector P, std::vector Q){ assert(!Q.empty() && Q[0] != 0); int z = 1; while (z < (int)std::max(P.size(), Q.size())) z *= 2; P.resize(z * 2, 0); Q.resize(z * 2, 0); atcoder::internal::butterfly(P); atcoder::internal::butterfly(Q); // fast while (k){ // Q(-x) std::vector Q_n(z * 2); for (int i = 0; i < z; i++){ Q_n[i * 2] = Q[i * 2 + 1]; Q_n[i * 2 + 1] = Q[i * 2]; } for (int i = 0; i < z * 2; i++){ P[i] *= Q_n[i]; Q[i] *= Q_n[i]; } FPS_pick_even_odd(P, k & 1); FPS_pick_even_odd(Q, 0); k /= 2; if (k == 0) break; FPS_extend(P); FPS_extend(Q); } T SP = 0, SQ = 0; for (int i = 0; i < z; i++) SP += P[i], SQ += Q[i]; return SP / SQ; // simple /* while (k){ auto n_Q = Q; for (int i = 0; i < int(Q.size()); i++){ if (i & 1) n_Q[i] *= -1; } auto n_P = atcoder::convolution(P, n_Q); n_Q = atcoder::convolution(Q, n_Q); for (int i = 0; i < int(Q.size()); i++){ Q[i] = n_Q[i * 2]; } P.clear(); for (int i = (k & 1); i < int(n_P.size()); i += 2){ P.push_back(n_P[i]); } k >>= 1; } return P[0] / Q[0]; */ } template // 0 = a[i] * c[0] + a[i - 1] * c[1] + a[i - 2] * c[2] + ... + a[i - d] * c[d] // a.size() + 1 == c.size() // c[0] = - 1 ? // return a[k] T Kth_Linear(long long k, std::vector a, std::vector c){ int d = a.size(); assert(d + 1 == int(c.size())); std::vector P = atcoder::convolution(a, c); P.resize(d); return Boston_Mori(k, P, c); } }; #line 26 "c.cpp" using mint = atcoder::modint998244353; void add(vector &a, vector &b, mint c = 1, int d = 0){ rep(i, 0, b.size()){ while ((int)a.size() <= i + d) a.push_back((mint)0); a[i + d] += b[i] * c; } } void solve(); // CITRUS CURIO CITY / FREDERIC int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t = 1; // cin >> t; rep(i, 0, t) solve(); } void solve(){ ll N, K; cin >> N >> K; vector f(K + 1); rep(i, 0, K) f[i + 1] = 1; vector A = {1}; add(A, f, -1); vector B = {1}; add(B, A, -1, 1); add(B, f, -1, K + 1); add(B, f, -1, 0); cout << po167::Boston_Mori(N + K, A, B).val() << "\n"; }