Multiplication

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

If \(C = A \diamond B\), then \[C[k] = \sum_{\max(i, j) = k} A[i] \cdot B[j] \bmod (10^9 + 7)\].

Work out sequence \(C = A \diamond B\) for given sequence \(A\) and \(B\).

Input

The first line contains a integer \(n\), which denotes the length of sequence \(A, B\).

The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\), which denote sequence \(A\).

The thrid line contains \(n\) integers \(b_1, b_2, \ldots, b_n\), which denote sequence\(B\).

(\(1 \leq n \leq 10^5, 0 \leq a_i, b_i \leq 10^9\))

Output

\(n\) integers, which denotes sequence \(C\).

Sample Input

2
1 2
3 4

Sample Output

3 18 

Source

ftiasch

Manager

Information
Solved Number114
Submit Number364
Problem Tags
implementation
math
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel