题目描述

输出杨辉三角形的前 $n$ 行。第一行为 $1$；每一行首尾均为 $1$，其他数等于上一行相邻两个数之和。

输入格式

一行一个整数 $n$。

输出格式

输出 $n$ 行，第 $i$ 行包含 $i$ 个整数，数之间用空格分隔。

样例

5

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

数据范围

$1\le n\le20$。