题目描述

给定 $n,x,k$，求下列式子的值：

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

答案对 $998244353$ 取模。

特殊地，定义 $0^0=1$。

函数 $\operatorname{popcnt}(x)$ 表示 $x$ 在二进制表示下 $1$ 的个数。

输入格式

一行，三个整数 $n,x,k$。

输出格式

输出一个数表示答案。

5 5 2

23

12345678 1919810 11451

69157901

999999999999 125432670 1000

154496571

提示

【数据范围】

本题采用捆绑测试。

对于所有数据：$0\le n\le 10^{12},0\le x\le 10^9,0\le k\le 10^5$。

子任务编号	$n\le$	$k\le$	分数
1	$10^6$	$10^5$	$7$
2	$10^8$		$8$
3	$10^{12}$	$0$	$5$
4		$1$	$10$
5		$2$
6		$100$
7		$10^3$	$15$
8		$10^4$
9		$10^5$	$20$