题目描述

给定一张有 $n$ 个节点和 $\dfrac{n(n-1)}2$ 条边的无向完全图。每条边 $(i,j)$ 带权：

$$W_{i,j}\in\{0,1\}.$$

对于所有 $0\le s<2^{n-1}$，计数满足下列条件的排列 $p$ 的数量 $V_s$：

对所有 $i\in[1,n-1]$，都有

$$W_{p_i,p_{i+1}} =\left\lfloor \frac{s}{2^{i-1}}\right\rfloor \bmod 2.$$

也就是说，$s$ 的二进制第 $i-1$ 位规定了路径上第 $i$ 条边的颜色。你需要对每一种长度为 $n-1$ 的 $0/1$ 边权序列，统计有多少个点排列的相邻边权序列恰好等于它。

输入格式

第一行一个整数 $n$。

接下来 $n$ 行，第 $i$ 行 $n$ 个整数，第 $j$ 个表示 $W_{i,j}$。

保证 $W_{i,j}=W_{j,i}$，$W_{i,i}$ 恒为 $0$ 且没有实际意义。

输出格式

输出一行 $2^{n-1}$ 个整数，第 $i$ 个整数为 $V_{i-1}$。

样例 1

输入

3
011
101
110

输出

0 0 0 6

样例 2

输入

4
0101
1000
0001
1010

输出

2 2 6 2 2 6 2 2

数据范围与约定

对于所有测试数据，满足：

$$1\le n\le 19.$$

子任务编号	特殊性质	分值
1	$n\le 10$	10
2	$n\le 14$	20
3	$n\le 15$	10
4	$n\le 16$	15
5	$n\le 17$
6	$n\le 18$
7	$n\le 19$