Where we were, where we are... Where will we be?

定义 $f(x,y)$ 为符合以下要求的 $0\leq z < 2^k$ 的 $c_z$ 之和：

• 对于任意 $0 \le i < k$，$z$ 在二进制下第 $i$ 位（即 $2^i$ 位）要么等于 $x$ 在二进制下的第 $i$ 位，要么等于 $y$ 在二进制下的第 $i$ 位。

给定长度为 $2^k$ 的序列 $a,b,c$（均为 0-indexed）。

对于 $i=0\sim k$，求

$$ d_i=\sum_{\substack{0\le x,y < 2^k\\ \operatorname{popcount}(x\oplus y)=i}} f(x,y)\,a_x b_y $$

对 $10^9+7$ 取模。

输入格式

第一行一个正整数 $k$。

第二行 $2^k$ 个非负整数，表示序列 $a$。

第三行 $2^k$ 个非负整数，表示序列 $b$。

第四行 $2^k$ 个非负整数，表示序列 $c$。

输出格式

一行，$k+1$ 个非负整数，表示 $d_0,d_1,\dots,d_k$，对 $10^9+7$ 取模。

样例

样例 1 输入

1
2 3
4 5
6 7

样例 1 输出

153 286

样例 2 输入

2
1 9 2 1
1 9 4 9
2 0 2 6

样例 2 输出

72 776 640

数据范围

对于所有数据，保证 $1\leq k\leq21$，$0\leq a_i,b_i,c_i < 10^9+7$。

本题共有 $21$ 个测试点，对于第 $i$ 个测试点有 $k=i$。每个测试点的分值如下表：

每个测试点依赖前一个测试点。

时间限制：$10\texttt{s}$

空间限制：$128\texttt{MB}$