B. Subset
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a set $$$S$$$ of first $$$N+1$$$ non-negative integers i.e. $$$S = \{0, 1, 2, ..., N\}$$$. Find number of ways of choosing a $$$K$$$ size subset of $$$S$$$ with the property that the XOR-sum of all chosen integers has exactly $$$B$$$ set bits in its binary representation (i.e. the bits that are equal to $$$1$$$). Since the answer can be large, output it modulo $$$998244353$$$.

Input

The only line of input contains three space-separated integers $$$N\ (1\le N\le10^9)$$$, $$$K\ (1\le K\le5000)$$$ and $$$B\ (0\le B\le30)$$$.

Output

Output a single line containing the answer.

Examples
Input
2 2 0
Output
0
Input
2 2 1
Output
2
Input
2 2 2
Output
1
Note

XOR-sum of $$$n$$$ integers $$$a_1,a_2,\cdots,a_n$$$ will be $$$a_1\ xor\ a_2\ xor\ \cdots\ a_n$$$. By xor, we mean bit-wise xor.