Pascal's triangle

Problem

In Pascal's triangle each row starts and ends with 1, and every other number is the sum of the two numbers above it:

`` 1 1 1 1 2 1 1 3 3 1 ``

Read n and print the first n rows. You have not learned arrays yet, so compute each number from the one before it in the same row.

Input: One integer n.
Output: n lines. Line r (counting from 0) has r + 1 numbers separated by single spaces.
Constraints: 1 ≤ n ≤ 30

Example

Input

Output

The fifth row is 1 4 6 4 1.

Try the problem first. Open one hint at a time.

Hint 1

Number k of row r is C(r, k), the number of ways to choose k items from r.

Hint 2

Each number follows from the one before it: C(r, k + 1) = C(r, k) × (r - k) / (k + 1). The first number is 1.

Hint 3

Multiply before dividing (the division is then always exact), and use long for the product.

Write your Java code, run it on the examples and submit it to hidden tests.