题目描述

打印杨辉三角形的前 $n$ 行。杨辉三角形中，第 $i$ 行有 $i$ 个数，第一个和最后一个数都是 $1$，其余每个数等于它上方两个数之和。例如 $n=5$ 时的杨辉三角形如下：

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

输入格式

一行一个整数 $n$，表示要打印的行数。

输出格式

共 $n$ 行，第 $i$ 行输出 $i$ 个整数，两两之间用一个空格隔开。每行的第一个数和最后一个数均为 $1$，中间的数按照杨辉三角的规律计算。

样例

5

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

数据范围

$2 \le n \le 50$