Good job helping Jason out on the previous problem!

Jimmy has developed an unfortunate situation, and needs your help right away! He is suffering from Acute Pascal Syndrome, and needs you to print out the first \(N\) rows of Pascal's triangle, mod \(10^9+7\), in order for him to be cured.

Please do so ASAP to save him!!

Constraints

\(1 \le N \le 10 ^ 3\)

Input Specification

The first line will contain one integer \(N\), the number of rows to print out.

Output Specification

Output the first \(N\) rows of Pascal's triangle, mod \(10^9+7\).

Sample Input

4

Sample Output

1
1 1
1 2 1
1 3 3 1