#1441. [NOIP2021] 数列

[NOIP2021] 数列

题目描述

给定整数 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 取模的结果。

输入格式

输入第一行是三个整数 n,m,kn, m, k。

第二行 m+1m + 1 个整数,分别是 v0,v1,…,vmv_0, v_1, \ldots, v_m。

输出格式

仅一行一个整数,表示所有合法序列的权值和对 998244353998244353 取模的结果。

样例

5 1 1
2 1
40
见附件中的 sequence/sequence2.in
见附件中的 sequence/sequence2.ans

题目来源:洛谷 P7961