Counting Sequences
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

You are given three integers n,m,k, You need to calculate the number of sequence A=(A_1,A_2,\dots,A_n) that satisfies both of the following conditions:

  • For each A_i(1\le i\le n), 0\le A_i<2^m.
  • We let sequence B be the sequence obtained by rotating sequence A once,

\sum_{i=1}^n cnt_1(A_i\oplus B_i)=k

Where \oplus represents bitwise XOR, one rotation operation will change (A_1,A_2,\dots,A_{n-1},A_n) to (A_2,A_3,\dots,A_n,A_{1}). cnt_1(x) represents the number of 1s in the binary representation of x.

输入描述:

One line containing 3 integers n,m,k (2\le n< 998244353, 1\le m\le 10^8, 1\le k\le 5\times 10^4).

输出描述:

Output one line containing an integer, representing the answer \text{mod}\ 998244353.
示例1

输入

复制 
2 1 2

输出

复制 
2
示例2

输入

复制 
2 2 2

输出

复制 
8
示例3

输入

复制 
2 3 2

输出

复制 
24

备注:

In the first example, A can be (0, 1) or (1, 0).

In the second example, A can be (0, 1), (0, 2), (1, 0), (1, 3), (2, 0), (2, 3), (3, 1), (3, 2).