Zayin 正在玩一款由 Tendollars 公司开发的名为《Battlegrounds》的趣味电脑游戏。 在这个游戏中，玩家可以使用 $m$ 种武器，例如 AK-47 突击步枪、霰弹枪、火箭推进榴弹等。这 $m$ 种武器编号为 $1$ 到 $m$。 玩家可以开始一场比赛。在一场比赛中，最多有一百名装备了武器的玩家跳伞降落到一个岛上并相互战斗。最后存活的玩家将赢得比赛。 对于同一种武器，玩家最多只能装备一把。因此，我们可以通过玩家拥有的武器集合来了解其实力。

首先，我想向你展示如何使用二进制数来表示武器集合。我们可以使用一个 $m$ 位的二进制数 $x$ 来表示一个集合 $S$。$x$ 的第 $i$ 位（从最低位到最高位）表示 $S$ 是否包含第 $i$ 种武器。当第 $i$ 位为 $1$ 时，集合包含第 $i$ 种武器。否则，集合不包含该武器。我们将数字 $x$ 称为集合 $S$ 的数值表示。为简单起见，在问题的其余部分，我们仅使用 $x$ 的十进制形式来描述集合 $S$。 例如，当 $x = 6$ 时，其二进制形式为 $110$，这意味着集合中包含第 $2$ 种和第 $3$ 种武器。

起初，Zayin 没有任何武器（他的武器集合可以表示为 $0$）。因此他很容易被其他玩家击败。Zayin 需要收集更多的武器来变得更强。 他将参加 $n$ 轮抽奖。在每一轮中，Tendollars 公司会展示 $k$ 个盒子，每个盒子包含某些类型的武器。Zayin 在这一轮中将恰好获得一个盒子，并获得该盒子中的所有武器。Zayin 获得第 $j$ 个盒子的概率为 $p_j (1 \le j \le k)$。由于公司程序员写了一些糟糕的代码，这些概率 $p_j (1 \le j \le k)$ 在各轮之间不会改变。第 $i$ 轮中第 $j$ 个盒子里的武器集合为 $a_{ij}$。

设 $f(x)$ 为 Zayin 最终获得的武器集合为 $x$ 的概率。 对于所有可能的集合 $x (0 \le x \le 2^m - 1)$，请计算 $f(x)$ 的值，模 $1000000007$。

输入格式

第一行包含三个整数 $n, m, k (1 \le n \le 100000, 1 \le m \le 16, 1 \le k \le 8)$，分别表示抽奖轮数、不同武器的数量以及每轮中盒子的数量。 第二行包含 $k$ 个整数 $b_1, b_2, \dots, b_k (0 \le b_j \le 1000000000)$。Zayin 在一轮中获得第 $j$ 个盒子的概率为 $p_j = \frac{b_j}{1000000000}$。保证所有 $b_j$ 之和为 $1000000000$。 接下来的 $n$ 行描述了每一轮中每个盒子里的武器集合。第 $i$ 行包含 $k$ 个整数 $a_{i1}, a_{i2}, \dots, a_{ik}$。$a_{ij}$ 是第 $i$ 轮中第 $j$ 个盒子的武器集合的数值表示。

输出格式

输出 $2^m$ 行，第 $x$ 行包含 $f(x - 1)$ 的值（模 $1000000007$），$x = 1, 2, \dots, 2^m$。

样例

输入格式 1

2 2 2
400000000 600000000
1 0
2 1

输出格式 1

0
200000002
680000005
120000001

说明

在上面的样例中，获得两个盒子的概率分别为 $\frac{2}{5}$ 和 $\frac{3}{5}$。 各轮之后集合的概率如下：

初始：00 为 1，01 为 0，10 为 0，11 为 0。 第 1 轮后：00 为 $\frac{3}{5}$，01 为 $\frac{2}{5}$，10 为 0，11 为 0。 第 2 轮后：00 为 0，01 为 $\frac{3}{5}$，10 为 $\frac{6}{25}$，11 为 $\frac{4}{25}$。