QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 256 MB Total points: 100

# 5376. xor

Statistics

给定 $n, d$,计算

$$\mathrm{ans} = \sum_{0 \leq x,y,z < n} (x \oplus y \oplus z)^d \bmod{998\,244\,353}$$

输入格式

两个整数 $n, d$。

输出格式

输出整数 $\mathrm{ans}$。

样例数据

样例输入

10 3

样例输出

718116

子任务

对于子任务 1($10\%$):$0 < n \leq 300$,$d \leq 3$。

对于子任务 2($10\%$):$0 < n \leq 5\,000$,$d \leq 3$。

对于子任务 3($20\%$):$0 < n \leq 10^5$,$d \leq 3$。

对于子任务 4($20\%$):$0 < n \leq 2^{30}$,$d \leq 3$。

对于子任务 5($20\%$):$0 < n \leq 2^{30}$,$d \leq 10$。

对于子任务 6($20\%$):$0 < n \leq 2^{30}$,$d \leq 10^5$。