小马与谐律精华

• 时间限制：5 秒
• 内存限制：256 MiB

题目描述

有 $n=2^m$ 个节点，编号为 $0,1,\ldots,n-1$。节点 $u$ 在时刻 $i$ 的能量记为 $e_i[u]$，其变化规律为

$$e_i[u]=\sum_{v=0}^{n-1}e_{i-1}[v]\cdot b_{\operatorname{popcount}(u\operatorname{xor}v)}.$$

给定初始能量向量 $e_0$、变换系数 $b_0,b_1,\ldots,b_m$、时刻 $t$ 与模数 $p$，求时刻 $t$ 的能量向量对 $p$ 取模后的结果。

输入格式

第一行包含三个整数 $m,t,p$。

第二行包含 $n=2^m$ 个整数 $e_0[0],e_0[1],\ldots,e_0[n-1]$。

第三行包含 $m+1$ 个整数 $b_0,b_1,\ldots,b_m$。

输出格式

输出 $n$ 行，第 $i$ 行为 $e_t[i]\bmod p$。

样例输入

2 2 10000
4 1 2 3
0 1 0

样例输出

14
6
6
14

数据范围

$1\le m\le20$，$0\le t\le10^{18}$，$2\le p\le10^9$；$1\le e_0[i]\le10^9$，$0\le b_i\le10^9$。

子任务编号	分值	特殊限制
1	20	$m\le3$ 且 $t\le8$
2	40	$m\le8$
3		无特殊限制

每个测试点独立计分。