Problem Background

JXCSP-S T2

Problem Description

Given two sequences \(a_i\) and \(b_i\) indexed from 1 to \(n\), define the function \(S(l,r)\) (where \(1 \le l \le r \le n\)) as:

\[ S(l,r) = \sum_{i=l}^r a_i \times \sum_{i=l}^r b_i \]

You are required to compute the value of the following expression:

\[ \sum_{l=1}^n \sum_{r=l}^n S(l,r) \]

Since the answer may be very large, you only need to output the result modulo \(10^9 + 7\).

Input Format

The first line contains a positive integer \(n\) representing the length of the sequences.
The second line contains \(n\) positive integers representing the sequence \(a_i\).
The third line contains \(n\) positive integers representing the sequence \(b_i\).

Output Format

Output a single integer representing the result modulo \(10^9 + 7\).

Sample Input and Output

Sample Input #1

3
2 3 4
3 4 5

Sample Output #1

244

Sample Input #2

5
11 22 33 44 55
12 34 56 78 90

Sample Output #2

201542

Notes

Data Range:
For 20% of the data: \(n \le 10\), \(a_i, b_i \le 10\);
For 40% of the data: \(n \le 200\), \(a_i, b_i \le 100\);
For 70% of the data: \(n \le 3000\), \(a_i, b_i \le 10^5\);
For 100% of the data: \(3 \le n \le 5 \times 10^5\), \(1 \le a_i, b_i \le 10^9\).

见题面 Input 部分

见题面 Output 部分