Pascal’s triangle is one of the most fascinating concepts in combinatorics and has so many applications. One of the ways it can be used is to determine the value of

(n choose k).The triangle is constructed by adding up its two parent cells. So, for instance, the 10 on the 6th line is constructed by adding 4 and 6 from the 5th line.

Given a height

`h`

, you are asked to construct Pascal’s triangle.The only line of the input contains the number

`h`

.The output of the program should be Pascal’s triangle of height

`h`

.```
Input
5
Output
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
```