题目描述

找到$N$个整数序列$A_0, \ldots, A_{N-1}$，定义如下。

• 对于每个$i$ $(0 \leq i \leq N-1)$，$A_i$的长度为$i+1$。
• 对于每个$i$和$j$ $(0 \leq i \leq N-1, 0 \leq j \leq i)$，$A_i$的第$(j+1)$个元素，记作$a_{i,j}$，定义如下。
  • 当$j=0$或$j=i$时，$a_{i,j}=1$。
  • 否则，$a_{i,j} = a_{i-1,j-1} + a_{i-1,j}$。

约束条件

• $1 \leq N \leq 30$
• $N$ 是一个整数。

输入

从标准输入中以以下格式给出输入：

$N$

输出

打印$N$行。第$i$行应该包含用空格分隔的$A_{i-1}$的元素。

示例输入 1

3

示例输出 1

1
1 1
1 2 1

示例输入 2

10

示例输出 2

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1