配点 : 100 点
問題文
正整数 N,M 。
由非负整数组成的长度 N 序列 对于 A ,满足以下条件的非负整数 X_{i,j}\ (1\leq j\leq i\leq N) 唯一存在。
- X_{i,1}=A_i\ (1\leq i\leq N)
- X_{i,j}=X_{i-1,j-1}\oplus X_{i,j-1}\ (2\leq j\leq i\leq N)
但是 \oplus 表示按位异或。 此时 \sum_{i=1}^{N}\sum_{j=1}^{i}X_{i,j} 的值 A 的 可以考虑 分数 对于每个 。
S=1,2,\dots,M ,由非负整数组成的长度 总和是 N 的序列 所有 S 的分数总和 除以 998244353 后求余数。
制約
- 1\leq N\leq 10^{9}
- 1\leq M\leq 10^{5}
- 所有输入均为整数
部分点
这个问题有多个部分点。 如果正确答案是满足
- N \leq 3000, M = 1 的数据集 如果满足 1 点。
- N \leq 10^6, M = 1 的数据集的答案是正确的,则附加 跨 1 点。
入力
输入是按以下格式从标准输入给出的。
N\ M
出力
M 线输出。 当i\ (1\leq i\leq M) 在线 S=i 时打印答案。
入力例 1
4 1
出力例 1
18
例如 自从 A=(0,1,0,0) 什么时候 X_{i,j} 如下,得分为 请打印除以 5 。
- X_{1,1}=0
- X_{2,1}=1,X_{2,2}=1
- X_{3,1}=0,X_{3,2}=1,X_{3,3}=0
- X_{4,1}=0,X_{4,2}=0,X_{4,3}=1,X_{4,4}=1
入力例 2
202515 1
出力例 2
631322682
998244353 后的余数。
入力例 3
1000000000 20
出力例 3
450736580 222005843 791558300 565944390 287066035 818826101 538663305 222889651 450257059 718428507 230132846 653810630 380943894 21756026 863202268 823515972 834078326 615162787 221193562 85328814