Pascal's Triangle Generator

Given a positive integer (N), generate the first (N) lines of Pascal's Triangle. In Pascal's Triangle, every entry is the sum of the two entries directly above it. Formally, the entries satisfy the recurrence relation:

[ T(n,k) = T(n-1,k-1) + T(n-1,k) \quad (1 < k < n), ]

with the boundary conditions (T(n,1)=T(n,n)=1). Each line should be printed as a string of numbers separated by a single space. If (N \le 0), no output should be produced.

Examples:

Input: 4

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

inputFormat

The input consists of a single integer (N) read from STDIN.

outputFormat

Print the first (N) lines of Pascal's Triangle, each on a separate line. Every line should contain the elements of the row separated by a single space. For (N \le 0), output nothing.## sample

1

1