[NOIP2021]数列（sequence）
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

    给定整数 n, m, k ，和一个长度为  的正整数数组 。
    对于一个长度为 n，下标从 1 开始且每个元素均不超过 m 的非负整数序列 ，我们定义它的权值为 。

    当这样的序列  满足整数  的二进制表示中 1 的个数不超过 k 时，我们认为  是一个合法序列。

    计算所有合法序列  的权值和对 998244353 取模的结果。

输入描述:

输入的一行是三个整数 n, m, k。
第二行 个整数，分别是 。

输出描述:

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

输入

复制 
5 1 1
2 1

输出

复制 
40

说明

由于 k= 1，而且由 n ≤ S ≤ n ×2^m 知道 5≤ S ≤10，合法的S只有一种可能：S = 8，这要求 a 中必须有 2 个 0 和 3 个 1 ，于是有 \left(\begin{array}{l}5 \\ 2\end{array}\right)=10 种可能的序列，每种序列
的贡献都是 v_{0}^{2} v_{1}^{3}=4，权值和为 10 × 4 = 40。

备注:

对所有测试点保证 。