Array Interval Sum Game

Alice plays an interval sum game with an integer array. The game goes as follows.

• First, create an array $A$ of length $n$ made of $n$ distinct integers. The elements are $A[1], \dots, A[n]$.
• Next, choose $m$ pairs of integers $(x_1, y_1), \dots, (x_m, y_m)$ that describe intervals of $A$. Each pair must satisfy $1 \le x_i \le y_i \le n$.
• The interval sum is defined as $S(A, x, y) = \sum_{j=1}^{m} \left( \sum_{i=x_j}^{y_j} A[i] \right)$
• The goal is to rearrange the elements of $A$ in any order so that $S(A, x, y)$ is as large as possible. Since there are $n$ elements, there are $n!$ possible rearrangements.

For example, let $n = 3$, $m = 2$, $A = [10, 100, 1000]$, $x = [1, 2]$, and $y = [2, 2]$. The largest possible value is $2100$, and the rearrangement $[100, 1000, 10]$ is the only one that reaches it.

Another example: let $n = 2$, $m = 1$, $A = [20, 22]$, $x = [1]$, and $y = [2]$. The largest possible value is $42$, and both rearrangements reach it.

Given $A$, $x$, and $y$, find the largest value of $S(A, x, y)$ that Alice can reach by rearranging $A$, and count how many rearrangements reach that value.

The first line contains the number of test cases $T$.

Each test case starts with a line containing $n$ and $m$, separated by a space. The second line contains the $n$ elements of $A$, separated by spaces. Each of the next $m$ lines contains two integers $x_i$ and $y_i$, separated by a space.

For each test case, print the maximum value of $S(A, x, y)$ and the number of rearrangements that reach it, separated by a space. Print the count modulo $10^9+7$.

• $1 \le T \le 10$
• $1 \le n \le 50\,000$
• $1 \le m \le 200\,000$
• $1 \le$ each element of $A \le 10^8$
• The elements of $A$ are distinct
• For every integer $i$ with $1 \le i \le m$, $1 \le x_i \le y_i \le n$