# Grox的序列七

- 参考时间限制：1.0 秒。
- 实际时限：标准程序在目标环境的最慢用例中位耗时乘以 2，再按 0.5 秒向上取整。
- 内存限制：128 MB。
- [参考评测环境与测量](../../../docs/评测环境与性能.md)

## 背景故事

> 我们的一些理论家认为Grox行为的动机，可能就是机械与有机生命体的差异性，然而没有任何方式能够检验这个假说。
>
> ——科学之书10（《Spore》，[英文资料](https://spore.fandom.com/wiki/Books_of_Science)）

Grox 的思维令人着迷。经过长期的半机械化改造，他们的思考方式已经与其他生物大不相同，甚至包含矩阵的行列式。

你想起那个浪漫的文字矩阵：

$$\det\begin{pmatrix}\text{我}&0&\text{生}\\0&\text{有}&0\\\text{你}&0&\text{幸}\end{pmatrix}=\text{我有幸}-\text{生有你}$$

把减号看成汉字“一”，就成了“我有幸，一生有你”。不过，Grox 这次交来的既不是文字矩阵，也不是普通的数字矩阵，而是一个多项式矩阵；行列式的计算规则仍然相同。

Grox 想得到这个行列式的系数序列。由于项数和系数都可能很大，你需要按指定方式汇总系数，再将结果取模。

## 形式化问题描述

给定整数 $k$ ，令 $N=2^k$ .输入 $N$ 个多项式，按 $1$ 到 $N$ 编号：

$$A_i(x)=\sum_{j=0}^{N-1}a_{i,j}x^j$$

构造 $N\times N$ 多项式矩阵 $M$ ，其中

$$M_{r,i}=A_i(x)^{r-1}\qquad(1\le r,i\le N)$$

第一行各元素均为常数多项式 $1$ ，包括 $A_i(x)=0$ 的情况。令

$$B(x)=\det M=\sum_{t\ge0}b_t x^t$$

对 $0\le r<N$ ，计算

$$V_r=\left(\sum_{\substack{t\ge0\\t\equiv r\pmod N}}b_t\right)\bmod P\qquad(P=1004535809)$$

也就是把指数对 $N$ 取余后，将同类项的系数相加。输出各系数的最小非负余数。

## 输入格式

第一行一个整数 $k$ .接下来 $N$ 行，第 $i$ 行给出 $N$ 个整数 $a_{i,0},\ldots,a_{i,N-1}$ ，按次数从低到高排列。

## 输出格式

输出一行 $N$ 个整数 $V_0,\ldots,V_{N-1}$ ，以空格分隔。

## 样例

### 样例 1

### 输入

```text
1
1 2
3 4
```

### 输出

```text
2 2
```

### 样例 2

### 输入

```text
0
999
```

### 输出

```text
1
```

### 样例 3

### 输入

```text
2
1 2 3 4
7 8 9 10
1 2 3 4
5 6 7 8
```

### 输出

```text
0 0 0 0
```

## 样例解释

样例一的行列式为 $(3+4x)-(1+2x)=2+2x$ .样例二为一阶矩阵，行列式为 $1$ .样例三有两列相同，行列式为零多项式。

## 数据范围与保证

对 **100% 数据**：

$0\le k\le9$ ；$0\le a_{i,j}\le999$ .

| 分值比例 | 额外条件 |
| --- | --- |
| 100% | 无额外条件 |