题目描述

求定义如下的 $N$ 个整数序列 $A_1,\ldots,A_{N}$ 。

• 对于每个 $i$ $(1\leq i \leq N)$ ， $A_i$ 的长度为 $i$ 。
• 对于每个 $i$ 和 $j$ $(1\leq i \leq N, 1 \leq j \leq i)$ ， $A_i$ 的第 $j$ 项（用 $a_{i,j}$ 表示）定义如下。
  • 若满足 $j=1$ 或 $j=i$，则 $a_{i,j}=1$
  • 否则，$a_{i,j} = a_{i-1,j-1} + a_{i-1,j}$ 。

现在你需要打印出 $a$ 具体可以理解样例。

输入格式

第一行输入整数 $N$

输出格式

输出一共输出 $N$ 行，每一行输出 $i$ 个数字，分别用空格隔开。

3

1
1 1
1 2 1

10

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

提示

数据范围

• $1\ \leq\ N\ \leq\ 30$
• $N$ 是整数