sub1 里是暴力，是正确的，只求调 sub2，思路是枚举 $S$ 的值并进行 $dfs$，其中 $(x,res)$ 代表需要用 $res$ 个位置凑出 $x$，调了四个晚上了。

#include<iostream>
#include<cstdio>
#include<cstring>
#define lowbit(x) ((x)&(-x))
#define int long long
#define CI const int
const int N=35,P=998244353,inf=1e9;
using namespace std;
int T,n,m,k,v[N];
int read(int& v)
{
	char ch;int f=1;
	for(ch='*';!isdigit(ch) && ch!='-';ch=getchar());
	if(ch=='-')  f=-1,ch=getchar();
	for(v=0;isdigit(ch);v=v*10+ch-'0',ch=getchar());
return v;
}
int power(int a,int b)
{
	a%=P;
	int rec=1;
	for(;b;a=a*a%P,b>>=1)
		if(b&1)  rec=rec*a%P;
return rec;
}
int cnt(int x)
{
	int rec=0;
	while(x)  rec++,x-=lowbit(x);
	return rec;
}
namespace sub1
{
	int ans,p[N];
	void dfs(int id,int res,int x,int val,int t)
	{
		if(res==0)
		{
			if(cnt(x)>k)  return;
			ans=(ans+val*p[n]%P*t%P)%P;
			return;
		}
		if(id>m)  return;
		for(int i=0;i<=res;i++)   dfs(id+1,res-i,x+(1<<id)*i,val?val*power(v[id],i)%P:power(v[id],i),t*power(p[i],P-2)%P);
	}
	void main()
	{
		p[0]=1;
		for(int i=1;i<=n;i++)  p[i]=p[i-1]*i%P;
		dfs(0,n,0,0,1);printf("%lld\n",ans);
	}
}//20pts
namespace sub2
{
	const int M=2e5+5;
	int ans,maxv,mmp[M][N];
	int dfs(int x,int res)
	{
		int rec=0;
		if(x>res*(1<<m) || x<res)  return -1;
		if(res==0 && x==0)  return 0;
		if(res==0 || x==0)  return -1;
		if(mmp[x][res])  return mmp[x][res];
		for(int i=m;i>=0;i--)
			if(x>=(1<<i))
			{
				int tmp=dfs(x-(1<<i),res-1);
				if(tmp==0)  rec=(rec+v[i])%P;
				if(tmp>0)   rec=(rec+tmp*v[i]%P)%P;
			}
		return mmp[x][res]=rec;
	}
	void main()
	{
		maxv=(1<<m)*n;
		for(int i=1;i<=maxv;i++)
		{
			int rec=dfs(i,min(n,i));
			if(cnt(i)<=k && i>=n && rec>0)  ans=(ans+rec)%P;
		}
		printf("%lld\n",ans);
	}
}
void solve()
{
	read(n),read(m),read(k);
	for(int i=0;i<=m;i++)  read(v[i]),v[i]%=P;
//	if(n<=8){ sub1::main(); return; }
	if(n<=30){ sub2::main(); return; }
}
signed main()
{
//	freopen("sequence2.in","r",stdin);
//	freopen("sequence.out","w",stdout);
	/*read(T);
	while(T--)*/  solve();
return 0;
}