You are given integers ~n, m, k~ and ~m+1~ positive integers ~v_0, v_1, \dots, v_m~.

For a one-based array ~\{a_i\}~ containing ~n~ integers between ~0~ and ~m~, its weight is defined as ~v_{a_1} \times v_{a_2} \times \dots \times v_{a_n}~.

Such an array ~\{a_i\}~ is valid if ~S = 2^{a_1} + 2^{a_2} + \dots + 2^{a_n}~ contains no more than ~k~ ones in its binary representation.

Calculate the sum of weights of all valid arrays ~\{a_i\}~. Output the sum modulo ~998\,244\,353~.

Input Specification

The first line contains ~3~ integers ~n, m, k~.

The second line contains ~m+1~ integers ~v_0, v_1, \dots, v_m~.

Output Specification

Output a single integer, the sum of weights of all valid arrays modulo ~998\,244\,353~.

Sample Input

5 1 1
2 1

Sample Output

40

Sample 1 Explanation

Because ~k~ is ~1~ and ~n \le S \le n \times 2m~ implies ~5 \le S \le 10~, there is only one possible ~S~: ~S = 8~. This requires that ~a~ contains two ~0~s and three ~1~s. Thus, we have ~\left(\begin{array}{c}5\\2\end{array}\right)=10~ valid arrays. Each array has weight ~v_0^2 v_1^3 = 4~. The sum is ~40~.

Additional Samples

Additional samples can be found here.

Constraints

For all test cases, ~1 \le k \le n \le 30~, ~0 \le m \le 100~, ~1 \le v_i < 998\,244\,353~.

Test cases	~n~	~k~	~m~
~1\sim 4~	~=8~	~\le n~	~=9~
~5\sim 7~	~=30~		~=7~
~8\sim 10~			~=12~
~11\sim 13~		~=1~	~=100~
~14\sim 15~	~=5~	~\le n~	~=50~
~16~	~=15~		~=100~
~17\sim 18~	~=30~		~=30~
~19\sim 20~			~=100~