从 fft 和 ntt 过来的人，仔细看题意，别看错了！

按位与卷积（Bitwise AND Convolution）

问题描述

给定两个长度为 $2^N$ 的整数序列 $a_0, a_1, \dots, a_{2^N-1}$ 和 $b_0, b_1, \dots, b_{2^N-1}$，计算它们的按位与卷积序列 $c_0, c_1, \dots, c_{2^N-1}$，定义为：

$$c_k = \sum_{\substack{i,j \\ i \,\&\, j = k}} a_i \cdot b_j \bmod 998244353,$$

其中 $i \,\&\, j$ 表示按位与运算。

约束条件

• $0 \leq N \leq 20$
• $0 \leq a_i, b_i < 998244353$

输入格式

$N$
$a_0\ a_1\ \cdots\ a_{2^N-1}$
$b_0\ b_1\ \cdots\ b_{2^N-1}$

输出格式

$c_0\ c_1\ \cdots\ c_{2^N-1}$

3
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16

957 412 515 208 751 292 337 128