题面 下发文件

题目描述

给定 $n$ 和一个大小为 $(n+1)×(n+1)$ 的 $01$ 矩阵 $A$ ，矩阵下标从 $0$ 开始编号。保证这个矩阵满足 $A=A^{T}$ 。

我们称一棵树是合法的，当且仅当：令 $d_i$ 是点 $i$ 的度数，则树上的每一条边 $u,v$ 都要满足 $A_{d_u,d_v}=1$ 。

令 $f(n)$ 为 $n$ 个点的合法无标号无根树个数。

请求出 $f(3),f(4),\dots,f(n)$ 对给定质数 $P$ 取模的结果。

输入格式

第一行包含两个整数 $n,P$ 。

接下来 $n+1$ 行，第 $i$ 行包含 $n+1$ 个整数，其中第 $j$ 个整数代表 $A_{i,j}$。

输出格式

输出一行 $n-2$ 个整数，第 $i$ 个整数代表 $f(i+2)$ 。

样例

样例输入1

7 148600471
0 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1
1 1 0 1 1 1 1 1
1 1 1 0 1 1 1 1
1 1 1 1 0 1 1 1
1 1 1 1 1 0 1 1
1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 0

样例输出1

1 1 2 3 6

样例 2~5

见下发文件。

数据范围

对于所有数据，保证 $3\le n\le 150$ 。

$\forall 1\le i,j\le n+1,0 \le A_{i,j}<2$ 且 $A_{i,j}=A_{j,i}$ 。

保证 $P$ 为质数且 $10^8\le P\le 10^9+7$ 。

特殊性质 A: $\forall 1\le i\le j\le n+1,A_{i,j}=[i\neq j]$ 。