Description

Given integers $n, x, k$, compute the value of the following expression:

where the result is taken modulo $998244353$.

Special Note: $0^0$ is defined as $1$.

Here, $\text{popcnt}(x)$ denotes the number of $1$'s in the binary representation of $x$.

Input Format

A single line containing three integers $n, x, k$.

Output Format

Output a single integer representing the answer.

5 5 2

23

12345678 1919810 11451

69157901

999999999999 125432670 1000

154496571

Hint

Constraints

This problem uses subtask scoring.

For all test cases:

• $0 \leq n \leq 10^{12}$,
• $0 \leq x \leq 10^9$,
• $0 \leq k \leq 10^5$.