题目描述

输出杨辉三角的数字序列。

杨辉三角是一个二维形式的数字序列，第i行有i个数，每行的第一个数和最后一个数都是1，其他的每个数等于该数的上一行同一列的数加上上一行前一列的数的和。具体可以参考样例

输入

输入整数n，1<=n<=20

输出

输出n行杨辉三角序列

输入样例

5

输出样例

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