Cho mảng \(A\) gồm N phần tử. Nhiệm vụ của bạn là tìm \(Max = A_0 * 0 + A_1 * 1 +...+ A_{N - 1} * (N - 1)\) bằng cách sắp đặt lại các phần tử trong mảng. Chú ý, kết quả của bài toán có thể rất lớn, vì vậy bạn hãy đưa ra kết quả lấy modulo với \(10^9+7\).

Input

• Dòng đầu tiên đưa vào số lượng bộ test \(T\) (\(1 \leq T \leq 100\)).
• Những dòng kế tiếp đưa vào các bộ test. Mỗi bộ test gồm \(2\) dòng:
• Dòng thứ nhất đưa vào số nguyên \(N\) (\(1 \leq N \leq 10^7\)).
• Dòng tiếp theo đưa vào \(N\) số \(A_i\) (\(0 \leq i < N, 1 \leq A_i \leq 10^7\)) tương ứng với các phần tử của mảng \(A\); các số được viết cách nhau một vài khoảng trống.
• Tổng các số \(N\) của \(T\) bộ test không quá \(10^7\).

Output

• Đưa ra kết quả mỗi test theo từng dòng.

Example

2
5
5 3 2 4 1
3
1 2 3

40
8