BlueBook

Given an integer $N$, output the first $N$ rows of Pascal's triangle.

Input Specification

A single integer $N$ $(1\le N\le 20)$.

Output Specification

The first $N$ rows of Pascal's triangle, in order from top to bottom. Each row should be printed in a separate line, and the entries in each row should be printed from left to right with exactly one space between each pair of horizontally adjacent entries.

Sample Input

3

Sample Output

1
1 1
1 2 1