Pascal Triangle ⭐⭐⭐

Pascal’s Triangle is a triangular array of binomial coefficients. Each number is the sum of the two directly above it.

Write a program that reads an integer $N$ and prints the first $N$ rows of the triangle in a single line, separated by spaces.

Input

An integer $N$ ($1 \le N \le 20$).

Output

All numbers in the triangle up to row $N$, printed sequentially and separated by a space.

Example

Input: 4

Output: 1 1 1 1 2 1 1 3 3 1