问题 F: Counting Sequences

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

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

∑i=1ncnt1(Ai⊕Bi)=k\sum_{i=1}^n cnt_1(A_i\oplus B_i)=k∑i=1ncnt1(Ai⊕Bi)=k

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

One line containing $3$ integers n,m,kn,m,kn,m,k ($2\le n<998244353$, 1≤m≤1081\le m\le 10^81≤m≤108, 1≤k≤5×1041\le k\le 5\times 10^41≤k≤5×104).

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

2 1 2

2

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)$.