1007. Multicon

题目描述

对非负整数 $x$，定义 $x_i = \lfloor \frac{x}{6^i} \rfloor \bmod 6$，即 $x$ 在 $6$ 进制下第 $i$ 位的值。

对非负整数 $x,y$，定义运算 $x \otimes_6 y = \sum_{i \ge 0} ((x_i \times y_i) \bmod 6)6^i$，即 $6$ 进制下不进位乘法。

给出长为 $6^n$ 的非负整数序列 $a,b$，求序列 $c$，其中 $c_k = (\sum_{i \otimes_6 j = k} a_i \times b_j) \bmod (10^8+7)$，即计算 $6$ 进制下不进位乘法卷积。

请注意模数是 $10^8+7$。

输入格式

第一行包含一个整数 $T$（$1 \le T \le 2$）表示测试数据组数。

对每组测试数据：

• 第一行包含一个整数 $n$（$1 \le n \le 8$）。

• 第二行包含 $6^n$ 个整数 $a_0,a_1,a_2,\dots,a_{6^n-1}$（$0 \le a_i< 10^8+7$）。

• 第三行包含 $6^n$ 个整数 $b_0,b_1,b_2,\dots,b_{6^n-1}$（$0 \le b_i < 10^8+7$）。

输出格式

对每组测试数据，输出一行包含 $6^n$ 个整数 $c_0,c_1,c_2,\dots,c_{6^n-1}$，表示答案。

样例输入

2
1
1 1 1 1 1 1
1 1 1 1 1 1
2
0 6 7 3 0 6 0 7 9 7 9 6 6 9 4 9 8 0 1 8 5 3 6 3 4 7 4 1 0 3 9 9 1 2 8 5
7 5 7 6 9 9 0 1 9 1 9 0 5 2 3 5 7 8 5 6 9 4 2 6 3 1 1 0 3 2 5 0 0 2 0 7

样例输出

15 2 6 5 6 2
4376 803 2465 1538 2545 930 413 42 344 73 295 69 1367 158 615 324 712 220 1290 257 954 410 822 287 1531 115 616 415 620 257 451 51 271 107 278 54

提示

请注意模数是 $10^8+7$。

请使用较快速的输入输出方法，附件代码以 A + B Problem 为例，提供一份文件 IO 下简略的输入输出模板。

调用 $\text{IO::R()}$ 输入并返回一个 $\text{int}$ 范围内的非负整数，调用 $\text{IO::W()}$ 输出一个 $\text{int}$ 范围内的非负整数，并输出一个字符。

请保证输入文件的最后一个字符是空格或换行，即不是要读取的数字字符，数据中保证了这一点。请在程序结束运行前调用 $\text{IO::flush()}$ 以刷新输出缓冲区。

来源：2026杭电多校-测试专用（山西实验） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1234&pid=1007