You are given a complete graph with \(n\) nodes. There are two values associated with each node \(i\), denoted by \(a_i\) and \(b_i\).

The weight of the edge between two nodes \(i\) and \(j\) is denoted by \(w_{ij} = |a_ib_j-a_jb_i|\).

Find the sum of the square of weights of all the edges. Formally, find the value \(\sum_\limits{i=1}^n\sum_\limits{j=i+1}^nw_{ij}^2\).

Input format

Output format

Print a single integer denoting the required value (mod \(10^9+7\)).

Constraints

\(2\le n\le 10^6\\-10^{15}\le a_i,b_i\le 10^{15} \)