168. Pascal's Triangle
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
This problem is worth 30 points.

First envisioned by the French mathematician, Blaise Pascal, Pascal's Triangle is a formation of numerals that are arranged in such a way that a number composing a part of the triangle is the summation of the adjacent binomial pair of the previous row in the triangle.

Input

The only line of input contains a single positive integer $$$n$$$.

Output

Output $$$n$$$ lines. The $$$i$$$th line should contain $$$i$$$ space-separated integers, consisting of the $$$i$$$th row of Pascal's Triangle.

Example
Input
5
Output
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1