#include using namespace std; #include using namespace atcoder; #define int long long const long long inf=1LL<<62; using mint=atcoder::modint998244353; template class dynamic_lazy_segtree{ public: dynamic_lazy_segtree(int n):n(n){root=new node(e(),id(),n);} void set(int p,S x){ assert(p int max_right(int l)const{ return max_right(l,[](S x){return f(x);}); } template int max_right(int l,const G& f)const{ assert(l<=n); S product=e(); assert(f(product)); return max_right(root,0,n,l,f,product); } template int min_left(int r)const{ return min_left(r,[](S x){return f(x);}); } template int min_left(int r,const G& f)const{ assert(r<=n); S product=e(); assert(f(product)); return min_left(root,0,n,r,f,product); } void dump(){ dump(root,0,n);cout<>1; value=op(left?left->value:mapping(lazy_acc,e(),m-l),right?right->value:mapping(lazy_acc,e(),r-m)); return; } void eval(int l){ value=mapping(lazy,value,l); if(left)left->lazy=composition(lazy,left->lazy); if(right)right->lazy=composition(lazy,right->lazy); lazy_acc=composition(lazy,lazy_acc); lazy=id(); return; } }; int n; node* root; void set(node* t,int l,int r,int p,S x)const{ t->eval(r-l); int m=(l+r)>>1; if(l==p&&r==p+1){ t->value=x; return; }else{ if(!t->left)t->left=new node(e(),t->lazy_acc,m-l); if(!t->right)t->right=new node(e(),t->lazy_acc,r-m); } if(pleft,l,m,p,x); }else{ set(t->right,m,r,p,x); } t->update(l,r); } S get(node* t,int l,int r,int p)const{ t->eval(r-l); if(l==p&&r==p+1){ return t->value; } int m=(l+r)>>1; if(pleft?get(t->left,l,m,p):mapping(t->lazy_acc,e(),1); else return t->right?get(t->right,m,r,p):mapping(t->lazy_acc,e(),1); } void apply(node* t,int l,int r,int a,int b,F f)const{ t->eval(r-l); if(b<=l||r<=a)return; if(a<=l&&r<=b){ t->lazy=composition(f,t->lazy); t->eval(r-l); return; } int m=(l+r)>>1; if(!t->left){ t->left=new node(e(),t->lazy_acc,m-l); } if(!t->right){ t->right=new node(e(),t->lazy_acc,r-m); } apply(t->left,l,m,a,b,f); apply(t->right,m,r,a,b,f); t->update(l,r); } S prod(node* t,int l,int r,int a,int b)const{ t->eval(r-l); if(b<=l||r<=a)return e(); if(a<=l&&r<=b)return t->value; int m=(l+r)>>1; return op(t->left?prod(t->left,l,m,a,b):mapping(t->lazy_acc,e(),max(0LL,min(m,b)-max(l,a))),t->right?prod(t->right,m,r,a,b):mapping(t->lazy_acc,e(),max(0LL,min(r,b)-max(m,a)))); } template int max_right(node* t,int l,int r,int L,const G& f,S &product)const{ t->eval(r-l); if(r<=L)return r; if(!f(product))return l; if(f(op(product,prod(t,l,r,L,n))))return r; int m=(l+r)>>1; int res=t->left?max_right(t->left,l,m,L,f,product):m; if(res!=m)return res; product=op(product,t->left?prod(t->left,l,m,L,n):mapping(t->lazy_acc,e(),m-l)); if(!f(product))return l; return t->right?max_right(t->right,m,r,L,f,product):r-1; } template int min_left(node* t,int l,int r,int R,const G& f,S &product)const{ t->eval(r-l); if(l>=R)return l; if(!f(product))return r; if(f(op(product,prod(t,l,r,0,R))))return l; int m=(l+r)>>1; int res=t->right?min_left(t->right,m,r,R,f,product):m; if(res!=m)return res; product=op(product,t->right?prod(t->right,m,r,0,r):mapping(t->lazy_acc,e(),r-m)); if(!f(product))return r; return t->left?min_left(t->left,l,m,R,f,product):l+1; } void dump(node* t,int l,int r){ t->eval(r-l); cout<<"("<value<<" "<lazy_acc<<"),"; int m=(l+r)>>1; if(t->left)dump(t->left,l,m); if(t->right)dump(t->right,m,r); } }; mint op(mint a,mint b){ return a+b; } mint e(){ return 0; } mint mapping(mint f,mint x,int l){ return x+f*l; } signed main(){ int n,k;cin>>n>>k; dynamic_lazy_segtree seg(n+1); seg.set(0,1); for(int i=0;i