Given an Array \(arr\) of Integers having length \(N\), find the maximum value of \(min(A[i, j]) \times sum(A[i,j])\) for all \(0 \le i \le j < N\) where \(A[i,j]\) denotes the non-empty subarray \([A_i, A_{i+1}, A_{i+2}, ..., A_{j-1}, A_j]\).

Since the product may be large, return the product modulo \(10^9 + 7\).

Note:

Testcases are generated such that the maximum product without modulo will fit in a 64-bit signed integer.

Input Format:

First line contains an integer \(T\), the number of test cases.
First line of each testcase contains an integer \(N\), the length of array.
Second line of each testcase contains \(N\) space seperated integers, the values of array.

Output Format:

For each testcase, output an integer, the maximum value of \(min(A[i, j]) * sum(A[i,j])\) across all subarrays modulo \(10^9 + 7\).

Constraints:

\(1 \le T \le 10\)
\(-10^5 \le A_i \le 10^5\)
\(1 \le N \le 10^5\)