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