For a given integer , print the first rows of Pascal's Triangle. Print each row with each value separated by a single space. The value at the row and column of the triangle is equal to where indexing starts from . These values are the binomial coefficients.

The Pascal Triangle

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

Input Format

A single line of input, integer .

Constraints

Output Format

Output the first rows of Pascal's triangle.

Sample Input

4  

Sample Output

1  
1 1  
1 2 1  
1 3 3 1