问题描述

我喜欢你，E_Space，所以这是一道博弈题。

小 $\textbf{A}$ 与小$\textbf{B}$ 喜欢图上的游戏，现在有一个 $n$ 个点的有向图 $G$，最初图上没有边。在接下来 $m$ 个时刻，每个时刻会发生下列事件：

• 随机选取 $u,v\in[1,n]$，在图 $G$ 上连接一条从 $u\rightarrow v$ 的有向边。

小 $\textbf{A}$ 和小 $\textbf{B}$ 喜欢黑白两种颜色，最初第 $i$ 个点有颜色 $c_i\in \{0,1,2\}$，如果 $c_i=0$ 就是黑色，$c_i=1$ 就是白色，$c_i=2$ 表示该点颜色未确定。

小 $\textbf{A}$ 和小 $\textbf{B}$ 会在 $m$ 个时刻后的图 $G$ 上做游戏，小 $\textbf{A}$ 与小 $\textbf{B}$ 会轮流选择图 $G$ 上一个还未染色的点进行染色，其中小 $\textbf{A}$ 先手。小 $\textbf{A}$ 和小 $\textbf{B}$ 认为黑白相间的边才是美丽的，但是边存在方向。小 $\textbf{A}$ 获得的分数是满足 $u\rightarrow v$ 且 $c_u=0,c_v=1$ 的边的条数，小 $\textbf{B}$ 获得的分数是满足 $u\rightarrow v$ 且 $c_u=1,c_v=0$ 的边的条数，令 $\textbf{Z}$ 为小 $\textbf{A}$ 的分数减去小 $\textbf{B}$ 的分数，小 $\textbf{A}$ 想要使 $\textbf{Z}$ 尽量大，而小 $\textbf{B}$ 想要使 $\textbf{Z}$ 尽量小，若双方都足够聪明，最终 $\textbf{Z}$ 的值会是多少？

小 $\textbf{A}$ 和小 $\textbf{B}$ 想要知道，对于所有可能的 $n^{2m}$ 种情况，最终 $\textbf{Z}$ 的和对 $10^9+7$ 取模后的值为多少。\udot{注意，这里认为两种情况不同，当前仅当存在某个时刻加入的有向边不同，同时，图 $G$ 中可能存在重边和自环}。

但是观战者小 $\textbf{C}$ 认为这太简单了，小 $\textbf{C}$ 想要知道，对于所有 $1\le N\le n,1\le M\le m$，若只关注图 $G$ 的前 $N$ 个点（即忽略后 $n-N$ 个点，图 $G$ 上只有 $N$ 个点）且 $m=M$ 时上述问题对应的答案。

输入格式

第一行两个整数 $n,m$，分别表示图 $G$ 的点数以及时刻数。

接下来一行包含 $n$ 个整数，第 $i$ 个整数表示 $c_i$。

输出格式

共 $n$ 行，每行包含 $m$ 个整数，第 $i$ 行第 $j$ 个整数表示当 $N=i,M=j$ 时对应的答案。

输入格式

3 2
0 1 2

输出格式

0 0
0 0
2 28

数据范围

对于 $100\%$ 的数据，$1\leq n,m\le 50$，$c_i\in \{0,1,2\}$。

特殊性质 A: $\forall i \in [1,n]$，$c_i\in \{0,1\}$。

特殊性质 B: 保证 $c_i=2$ 的个数不超过 $1$。