Tam giác số Pascal đến hàng n (Pascal Triangle: First n Rows)

Nguồn: Phước Hưng OJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho số nguyên $n$. In $n$ hàng đầu tiên của tam giác Pascal, với hàng đầu là hàng $i=0$ chứa một số 1, hàng thứ hai là $i=1$ chứa 1 1, và hàng cuối là $i=n-1$. Ở hàng $i$, phần tử cột $j$ ($0\le j\le i$) bằng tổ hợp $C(i,j)$. Các số trên mỗi hàng cách nhau đúng một dấu cách; không có dấu cách cuối hàng.

Input

Một dòng chứa số nguyên $n$.

Output

In đúng $n$ dòng Pascal, từ hàng $i=0$ đến $i=n-1$.

Subtask

• Subtask 1 (20%): $1\le n\le 5$.

• Subtask 2 (30%): $1\le n\le 10$.

• Subtask 3 (50%): $1\le n\le 15$.

Ví dụ

Ví dụ 1

Input:

4

Output:

1
1 1
1 2 1
1 3 3 1

Giải thích:

n=4: in từ hàng 0 đến hàng n-1; hai đầu mỗi hàng đều bằng 1.

Ví dụ 2

Input:

1

Output:

1

Giải thích:

n=1: in từ hàng 0 đến hàng n-1; hai đầu mỗi hàng đều bằng 1.