#include #include using namespace std; using namespace atcoder; typedef long long ll; using mint=modint998244353; ll M=4001; vector op(vector a,vector b){ vector c=convolution(a,b); vector r(min(M,(ll)(c.size())),0); for(ll i=0;i<(ll)(r.size());i++){ r[i]=c[i]; } return r; } vector e(){ vector r(1,1); return r; } int main(){ ll N,Q; cin>>N>>Q; vector K(Q); vector> que(Q,vector(4)); for(ll i=0;i>K[i]; K[i]--; for(ll j=0;j<4;j++){ cin>>que[i][j]; } } vector X=K; sort(X.begin(),X.end()); vector y(1,X[0]); ll L=X.size(); for(ll i=1;i Y; for(ll i=0;i> Z(L,vector(M,1)); vector> x(L,vector(M,1)); segtree,op,e> seg(x); vector p(M,1); vector q(1,1); ll R=N-L; while(R){ if(R&1){ q=op(p,q); } p=op(p,p); R>>=1; } ll I; for(ll i=0;i A=op(seg.all_prod(),q); mint ANS=0; for(ll j=que[i][2];j<=que[i][3];j++){ if((ll)(A.size())>j){ ANS+=A[j]; } } cout<