题目描述

矩阵$C$由数组$A$，$B$生成，生成方式如下：$C_{ij}=A_i×B_j+i×B_j+A_i×j+i×j$ 定义一个矩阵的价值为这个矩阵中最大的元素的值。 定义$F[k]$为：矩阵$C$的所有大小为$k×k$的子矩阵的值的和。 现在请你输出$F[1]，F[2],…,F[n]$对$10^9+7$取模的结果。 注：这里子矩阵要求连续，详情请参考样例。

输入

第一行一个数$N$，表示$A、B$的长度。 接下来两行，每行$N$个整数，分别表示数组$A，B$。

输出

输出一行$N$个整数，表示答案。

输入样例

3
4 1 9
3 4 1

输出样例

280 204 72

提示

【数据规模与约定】 对于30%的数据，$N≤50$； 对于50%的数据，$N≤3000$； 对于100%的数据，$N≤100000，0≤A_i,B_i≤10^7$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共8个测试点，非原站或官方原始数据。总分100分。