题目描述

给定 $n$ 个长度为 $2^k$ 的序列 $\{\{A_{i,j}\}^{2^k-1}_{j=0}\}_{i=0}^{n-1}$，求它们的 $\bmod\ 998244353$ 循环卷积。

换句话说，计算 $\{P_i\}_{i=0}^{2^k-1}$，其中：

$$P_d=\underbrace{\sum_{a_0=0}^{2^k-1}\sum_{a_1=0}^{2^k-1}\dots\sum_{a_{n-1}=0}^{2^k-1}}_{a_0\text{ 到 }a_{n-1}}[(\sum_{i=0}^{n-1}a_i)\&(2^k-1)=d]\prod_{i=0}^{n-1}A_{i,a_i} $$

输入格式

第一行两个正整数 $n$ 和 $k$。
接下来 $n$ 个非负整数 $A_{0,0},A_{1,0},\dots,A_{n-1,0}$。
定义 $f(x)=[(108616x)\oplus x]\bmod 2^{31} \bmod998244353$。
对于所有 $0\le i<n,1\le i<2^k$，$A_{i,j}$ 满足 $A_{i,j}=f(A_{i-1,j})$。

输出格式

一行 $2^k$ 个非负整数，依次表示 $P_0,P_1,\dots,P_{2^k-1}$。

2 2
108616 1082902

537942285 676861806 480034636 632663940

数据规模与约定

$\&,\oplus$ 分别是按位与和按位异或。

保证 $0\le A_{i,j}<998244353$。

本题有 $50$ 组测试数据。

测试点	$n=$	$k=$
$1$
$2$	$2$	$10$
$3\sim 4$		$17$
$5\sim 6$	$50$
$7$	$500$	$11$
$8\sim 9$	$100$	$17$
$10\sim 11$	$128$
$12\sim 14$	$150$
$15\sim 18$	$200$
$19\sim 20$	$250$
$21\sim 23$	$256$
$24\sim 25$	$300$
$26\sim 27$	$350$
$28\sim 30$	$400$
$31\sim 32$	$450$
$33\sim 36$	$500$
$36\sim 40$	$512$
$41\sim 43$	$600$
$44\sim 50$	$666$