#210. 数列

数列

题目描述

给定整数 n,m,kn, m, k,和一个长度为 m+1m + 1 的正整数数组 v0,v1,,vmv_0, v_1, \ldots, v_m

对于一个长度为 nn ,下标从 11 开始且每个元素均不超过 mm 的非负整数序列 {ai}\{a_i\} ,我们定义它的权值为 $v_{a_1} \times v_{a_2} \times \cdots \times v_{a_n}$ 。

当这样的序列 {ai}\{a_i\} 满足整数 S=2a1+2a2++2anS = 2^{a_1} + 2^{a_2} + \cdots + 2^{a_n} 的二进制表示中 11 的个数不超过 kk 时,我们认为 {ai}\{a_i\} 是一个合法序列。

计算所有合法序列 {ai}\{a_i\} 的权值和对 998244353998244353 取模的结果。

输入格式

从文件 sequence.in 中读入数据。 输入第一行是三个整数 n,m,kn, m, k 。 第二行 m+1m + 1 个整数,分别是 v0,v1,,vmv_0, v_1, \ldots, v_m

输出格式

输出到文件 sequence.out 中。 仅一行一个整数,表示所有合法序列的权值和对 998244353998244353 取模的结果。

5 1 1
2 1
40

样例1解释:

由于 k=1k = 1 ,而且由 nSn×2mn \leq S \leq n \times 2^m 知道 5S105 \leq S \leq 10 ,合法的 SS 只有一种可能:S=8S = 8 ,这要求 aa 中必须有 22003311 ,于是有 (52)=10\binom{5}{2} = 10 种可能的序列,每种序列的贡献都是 v02v13=4v_0^2 v_1^3 = 4 ,权值和为 10×4=4010 \times 4 = 40

样例2:

见选手目录下的 sequence/sequence2.insequence/sequence2.ans

数据范围

测试点 nn kk mm
141 - 4 =8= 8 n \leq n =9= 9
575 - 7 =30= 30 =7= 7
8108 - 10 =12= 12
111311 - 13 =1= 1 =100= 100
141514 - 15 =5= 5 n \leq n =50= 50
1616 =15= 15 =100= 100
171817 - 18 =30= 30 =30= 30
192019 - 20 =100= 100