Weighted Sequence Sum with Binary Constraint

You are given three integers n, m, and k, and an array of m+1 positive integers: \(v_0,v_1,\ldots,v_m\). Consider sequences \(a_1, a_2, \ldots, a_n\) of nonnegative integers (with indices starting from 1) where every \(a_i\) satisfies \(0\le a_i\le m\). The weight of a sequence is defined as

[ W(a_1, a_2,\ldots,a_n)=v_{a_1}\times v_{a_2}\times\cdots\times v_{a_n}. ]

For a given sequence, define:

[ S=2^{a_1}+2^{a_2}+\cdots+2^{a_n}. ]

The sequence is valid if the binary representation of \(S\) contains at most \(k\) ones. Your task is to compute the sum of the weights of all valid sequences modulo 998244353.

inputFormat

The first line contains three integers: n, m, and k.

The second line contains m+1 positive integers: v0 v1 ... vm.

outputFormat

Output a single integer, the sum of the weights of all valid sequences modulo 998244353.

sample

2 1 1
1 2

5