题解：

不是很懂这类题有什么意思。

可以正着做也可以反着做，反着做状态要少一点，常数小一点。

尝试状压DP，发现复杂度是$O(nk{2}^k)$，感觉很方，测了一下极限数据，发现非0状态只有$7000$多个，于是只存有用状态即可。

$n$甚至可以开到$500$。

如果$k$再小一点，有效状态更少，可以上矩阵快速幂，$n$甚至可以开$1e9$直接用转移矩阵的特征多项式艹过去。

好的我会记住把这个改成毒瘤题的

---

代码：

#include<bits/stdc++.h> #define ll long long #define re register #define cs const using std::cerr; using std::cout; cs int mod=998244353; inline int add(int a,int b){a+=b-mod;return a+(a>>31&mod);} inline int dec(int a,int b){a-=b;return a+(a>>31&mod);} inline int mul(int a,int b){ll r=(ll)a*b;return r>=mod?r%mod:r;} inline int po(int a,int b){ int r=1;for(;b;b>>=1,a=mul(a,a)) if(b&1)r=mul(r,a);return r; } inline void Inc(int &a,int b){a+=b-mod;a+=a>>31&mod;} inline void Dec(int &a,int b){a-=b;a+=a>>31&mod;} inline void Mul(int &a,int b){a=mul(a,b);} cs int N=1<<21|7; int n,k,lim,l,tmp,S; struct array{ int vis[N],val[N]; int st[N],tp; int &operator[](int o){ if(!vis[o]){ vis[o]=true; val[o]=0; st[++tp]=o; }return val[o]; } inline void clear(){ while(tp){ vis[st[tp]]=0; val[st[tp]]=0; --tp; } } }f; int st[N],val[N],tp; #undef zxyoi signed main(){ #ifdef zxyoi freopen("sequence.in","r",stdin); #else #ifndef ONLINE_JUDGE freopen("sequence.in","r",stdin);freopen("sequence.out","w",stdout); #endif #endif scanf("%d%d%d",&n,&k,&l);tmp=l%mod; lim=std::min(k-1,l);S=1<<k; l=l>k?(l-k)%mod:0;f[1]=1; for(int re i=1;i<=n;++i){ tp=f.tp; for(int re j=1;j<=tp;++j){ st[j]=f.st[j]; val[j]=f.val[st[j]]; }f.clear(); for(int re j=1;j<=tp;++j){ int s=st[j],vl=val[j]; if(l)Inc(f[s],mul(vl,l)); for(int re k=0;k<=lim;++k)if(!(S&(s<<k))) Inc(f[(s|(s<<k))&(S-1)],vl); } }int ans=0; for(int re i=1;i<=f.tp;++i)Inc(ans,f.val[f.st[i]]); cout<<dec(po(tmp+1,n),ans)<<"\n"; return 0; }