Description

找出按以下方式定义的N个整数序列 A~0~,…,A~N-1~。

对于每个 i(0≤i≤N−1)，A~i~的长度为 i+1。 对于每个 i 和 j (0≤i≤N−1,0≤j≤i)，A~i~ 的第 (j+1) 项，记为 a~i,j~，定义如下：

· 如果 j=0 或 j=i，则 a~i,j~ =1。 · 否则，a~i,j~ = a~i-1,j-1~ + a~i-1,j~。

Input Format

输入N。

Output Format

输出 N 行。 第 i 行应包含 A~i−1~的各项，用空格分隔。

3

1
1 1
1 2 1

10

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1

Hint

【数据范围】 1≤N≤30，N 是整数。