Pascal Triangle: First n Rows

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Given $n$, print the first $n$ rows of Pascal’s triangle, indexed $i=0,1,\ldots,n-1$. Row $i$ contains binomial coefficients $C(i,0),\ldots,C(i,i)$. Separate numbers by one space, without trailing spaces.

Input

One line contains integer $n$.

Output

Print exactly $n$ Pascal rows, indexed $0$ through $n-1$.

Subtasks

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

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

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

Examples

Example 1

Input:

4

Output:

1
1 1
1 2 1
1 3 3 1

Explanation:

Print rows 0 through n-1 of Pascal’s triangle.

Example 2

Input:

1

Output:

1

Explanation:

Print rows 0 through n-1 of Pascal’s triangle.