杨辉三角

题目描述

杨辉三角是组合数学中经典的数字三角形结构，其构造规则如下：

1. 第 $i$ 行（行号从 $1$ 开始）恰好包含 $i$ 个正整数；
2. 每行的首尾两个数字均为 $1$；
3. 对于第 $i$ 行第 $j$ 列（$1 < j < i$）的数字，满足递推关系：$$a_{i,j} = a_{i-1,j-1} + a_{i-1,j}$$

现在给定一个正整数 $n$，请你按规则输出杨辉三角的前 $n$ 行。

输入格式

输入仅一行，包含一个正整数 $n$。

输出格式

输出共 $n$ 行。 对于第 $i$ 行，输出 $i$ 个整数，相邻两个整数之间用单个空格分隔，表示杨辉三角第 $i$ 行的全部数字。

样例

样例输入

5

样例输出

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

数据范围

对于 $100\%$ 的测试数据，满足 $1 \le n \le 30$，保证所有运算结果在 32 位整数范围内。