Popcount Power Sum

Given three integers n, x, and k, compute the value of the following expression modulo $998244353$:

\[ S = \sum_{i=0}^n (-1)^{\operatorname{popcnt}(i)} (i+x)^k \]

Here, by convention, we define $0^0=1$. The function $\operatorname{popcnt}(i)$ returns the number of ones in the binary representation of i.

Your task is to compute and output S mod 998244353.

inputFormat

The input consists of a single line containing three space-separated integers:

• n: a non-negative integer.
• x: an integer.
• k: a non-negative integer.

outputFormat

Output a single integer, which is the value of the expression computed modulo 998244353.

sample

3 2 2

4