A. Coin
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

$$$n$$$ individuals are betting on coins, and Eric is ranked $$$x$$$ at the beginning. Each round will divide these $$$n$$$ individuals into $$$\frac{n}{2}$$$ groups, with each group playing one game. In each match, the probability of two people winning is equal. After each match, if the person at the bottom of the rankings wins, then the rankings of the two people are swapped, otherwise the rankings of the two people remain unchanged.

Find the expected ranking of Eric after $$$k$$$ rounds, modeling $$$998244353$$$.

Input

One line contains two integers $$$n,x,k(1\le n,k\le 10^{18},1\le x \le n)$$$, $$$n$$$ is even.

Output

One line contains one integer — the expected ranking of EricXie after $$$k$$$ rounds, modeling $$$998244353$$$.

Examples
Input
2 2 2
Output
499122178
Input
114 5 14
Output
34643733