Print Pascal's triangle with \(n\) rows, reducing every entry modulo \(1,000,000,007\).

Input

One line containing \(n\).

The input satisfies:

• \(1 \le n \le 100\)

Output

Print one row per line with values separated by single spaces.

Example

Input

1

Output

1