给定整数n, m, k，和一个长度为m + 1的正整数数组v0,v1,…,vm。
对于一个长度为n，下标从1开始且每个元素均不超过m的非负整数序列{ai}，我们定义它的权值为va1×va2×⋯×van。
当这样的序列{ai} 满足整数S=2a1+2a2+⋯+2an 的二进制表示中1的个数不超过k时，我们认为{ai} 是一个合法序列。
计算所有合法序列{ai}的权值和对998244353取模的结果。
输入第一行是三个整数n, m, k。
第二行m + 1个整数，分别是v0,v1,…,vm。
5 1 1
2 1
40
【样例解释 #1】
由于 k = 1，而且由n≤S≤n×2m 知道5≤S≤10，合法的 SS 只有一种可能：S = 8，这要求 a中必须有2个0和3个1，于是有(25)=10 种可能的序列，每种序列的贡献都是v02v13=4，权值和为10×4=40。
【数据范围】
对所有测试点保证1≤k≤n≤30，0≤m≤100，1≤vi<998244353。
| 测试点 | n | k | m |
|---|---|---|---|
| 1∼4 | =8 | ≤n | =9 |
| 5∼7 | =30 | ≤n | =7 |
| 8∼10 | =30 | ≤n | =12 |
| 11∼13 | =30 | =1 | =100 |
| 14∼15 | =5 | ≤n | =50 |
| 16 | =15 | ≤n | =100 |
| 17∼18 | =30 | ≤n | =30 |
| 19∼20 | =30 | ≤n | =100 |