题目描述

杨辉三角形又称 $Pascal$ 三角形，它的第 $i+1$ 行是$(a+b)^i$ 的展开式的系数。

它的一个重要性质是：三角形中的每个数字等于它两肩上的数字相加。

下面给出了杨辉三角形的前 $4$ 行：

1

1 1

1 2 1

1 3 3 1

输入格式

输入共一行，包含一个数 $n。$

输出格式

输出杨辉三角形的前 $n$ 行。每一行从这一行的第一个数开始依次输出它 $\%(10^9 + 7)$ 的值，中间使用一个空格分隔。

数据范围

$1 ≤ n ≤ 1000.$

输入样例：

4

输出样例：

1
1 1
1 2 1
1 3 3 1

注：

$(a + b) \% p = (a \% p + b \% p) \% p$

$(a - b) \% p = (a \% p - b \% p ) \% p$

$(a * b) \% p = (a \% p * b \% p) \% p$