矩阵求和

题目描述

矩阵$C$由数组$A$,$B$生成，生成方式如下：$C_{i,j}=A_{i} \times B_{j}+A_{i} \times j+B_{j} \times i+i \times j$。

定义一个矩阵的价值为这个矩阵中最大的元素的值。

定义$F[k]$为：矩阵$C$的所有边长为$k$的子矩阵的值的和。

现在请你输出$F[1]$,$F[2]$,$\cdots$,$F[n]$对$10^{9}+7$取模的结果。

输入格式

第一行一个数$n$，表示$A$,$B$的长度。

接下来两行，每行$n$个整数，分别表示数组$A$,$B$。

输出格式

一行$n$个数，表示答案。

数据范围与提示

• 对于$30\%$的数据，$n < 50$；
• 对于$50\%$的数据，$n < 3000$；
• 对于$100\%$的数据，$1 < n < 100000$，$0 \leq A_{i}$,$B_{i} \leq 10^{7}$。

样例

3
4 1 9
3 4 1

280 204 72