题目描述

杨辉三角是一类非常有趣的数阵。如图所示是一个 6 行的杨辉三角，杨辉三角最外层的数值均为 1，中间的数值则为正上方和左上角的两个数值相加。杨辉三角内的数就是组合数，n 层杨辉三角就可以用来计算所有 i<n 的组合数 C_i^j。

读入一个正整数 n，请编程打印一个 n 行的杨辉三角。杨辉三角中的数会很大，你只需要输出它们除以 $10^{9}+7$ 的余数。

输入格式

一个正整数 n≤2000。

输出格式

n 层杨辉三角。

数据范围与约定

n≤2000。

可见测试数据

输入数据 1

5

输出数据 1

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

输入数据 2

1

输出数据 2

1

输入数据 3

2

输出数据 3

1
1 1