Tam giác Pascal kích thước n là tam giác gồm n dòng được định nghĩa như sau:

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

Tại dòng thứ i:

a[i][0] = a[i][i] = 1

a[i][j] = a[i-1][j-1] + a[i-1][j]

Bạn hãy viết chương trình in ra một tam giác Pascal

Input

Là số nguyên n (1 <= n <= 50)

Output

Gồm n dòng của tam giác Pascal tương ứng. Trên dòng thứ i gồm i số nguyên, mỗi số cách nhau một khoảng trắng.

Sample

Input #1

5

Output #1

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

Input #2

3

Output #2

1
1 1
1 2 1

Problem source: NTUCoder.net