P11957 「ZHQOI R1」幂和

给定 $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$。

输出一个数表示答案。

**【数据范围】** **本题采用捆绑测试。** 对于所有数据：$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$ | $10^5$ | $8$ | | 3 | $10^{12}$ | $0$ | $5$ | | 4 | $10^{12}$ | $1$ | $10$ | | 5 | $10^{12}$ | $2$ | $10$ | | 6 | $10^{12}$ | $100$ | $10$ | | 7 | $10^{12}$ | $10^3$ | $15$ | | 8 | $10^{12}$ | $10^4$ | $15$ | | 9 | $10^{12}$ | $10^5$ | $20$ |