【问题描述】

有一个数字三角是我国古代著名数学家杨辉首先提出的，这个数字三角如下图所示：

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

现在给你一个正整数n，请你用递归算法给出杨辉的前n行。

【程序名】triangle

【输入数据】

输入文件共一行，包含一个正整数n（1≤n≤20）。

【输出数据】

输出文件共n行，即杨辉三角的前n行。每行包含若干正整数，这些正整数之间用一个空格隔开（不能有多余的空格），最后一个正整数后面没有空格。

【样例】

4

1
1 1
1 2 1
1 3 3 1