#pragma optimize("g",on) #pragma GCC optimize("inline") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("O3") #include using namespace std; using pii=pair; #define ll int #define int long long #define pb push_back #define F first #define S second #define ld long double #define all(v) v.begin(),v.end() #define rall(v) v.rbegin(),v.rend() #define maxel(v) *max_element(all(v)) #define minel(v) *min_element(all(v)) #define endl '\n' const int N=1e6+67,mod=1e9+7,INF=1e18+1488; vector prefix_func(string s){ int n=s.size(); vector pi(n); pi[0]=0; for(int i=1;i0 && s[i]!=s[j]){ j=pi[j-1]; } if(s[i]==s[j])j++; pi[i]=j; } return pi; } int binpow(int a,int b,int MOD){ a%=MOD; int res=1; while(b>0){ if(b&1)res=res*a%MOD; a=a*a%MOD; b>>=1; } return res; } int inv(int a,int MOD){ return binpow(a,MOD-2,MOD); } vector fact,invfact; void precompute(int MOD){ fact.assign(N,1); invfact.assign(N,1); for(int i=1;i=0;i--){ invfact[i]=invfact[i+1]*(i+1)%MOD; } } int nCr(int n,int k,int MOD){ if(k<0||k>n)return 0; return fact[n]*invfact[k]%MOD*invfact[n-k]%MOD; } int nPr(int n,int k,int MOD){ if(k<0||k>n)return 0; return fact[n]*invfact[n-k]%MOD; } int gcd(int a,int b){ while(b){ a%=b; swap(a,b); } return a; } int lcm(int a,int b){ if(a==0||b==0)return 0; return a/gcd(a,b)*b; } struct DSU{ vector p,sz; int comp; DSU(int n){ p.resize(n+1); sz.assign(n+1,1); for(int i=1;i<=n;i++)p[i]=i; comp=n; } int get(int v){ return p[v]=(p[v]==v?v:get(p[v])); } void unite(int a,int b){ a=get(a); b=get(b); if(a!=b){ if(sz[b]>sz[a])swap(a,b); p[b]=a; sz[a]+=sz[b]; comp--; } } }; vector primes; vector is_comp; void sieve(int n){ is_comp.assign(n+1,false); if(n>=2)primes.pb(2); for(int i=3;i<=n;i+=2){ if(!is_comp[i]){ primes.pb(i); for(int j=i*i;j<=n;j+=2*i){ is_comp[j]=true; } } } } int phi(int a){ int r=a; for(int i=2;i*i<=a;i++){ if(a%i==0){ while(a%i==0)a/=i; r-=r/i; } } if(a>1)r-=r/a; return r; } int countD(int n) { int cnt=0; for(int i=1;i*i<=n;++i){ if(n%i==0){ if (i*i==n){ cnt+=1; } else{ cnt += 2; } } } return cnt; } void solve(){ int n,m,k; cin>>n>>m>>k; int md=998244353; int s=1< d(s,1); for(int j=1;j nd(s,0); for(int m2=0;m2=k){ nd[m2]=(nd[m2]+d[m1])%md; } } } d=nd; } int ans=0; for(int i=0;i>t; while(t--){ solve(); } return 0; }