Generate Pascal's Triangle

Given an integer n ($1 \le n \le 30$) as input, generate the first n rows of Pascal's Triangle. Each row should be printed on a new line with the numbers separated by a single space. Pascal's Triangle is defined recursively; each number is the sum of the two numbers directly above it. For example, when n = 4, the triangle should be:

1
1 1
1 2 1
1 3 3 1

Use the standard input and output methods described in the input/output sections.

inputFormat

The input consists of a single integer n (where $1 \le n \le 30$), which represents the number of rows to generate in Pascal's Triangle.

outputFormat

Output the first n rows of Pascal's Triangle. Each row should be printed on a new line, and within a row, the numbers should be separated by a single space.## sample

1

1