배열 구간합 놀이

Alice는 정수 배열로 구간합 놀이를 한다. 게임은 다음 순서로 진행된다.

• 먼저 서로 다른 정수 $n$개로 이루어진 길이 $n$의 배열 $A$를 만든다. $A$의 원소는 $A[1], \dots, A[n]$이다.
• 다음으로 배열의 구간을 나타내는 정수 쌍 $(x_1, y_1), \dots, (x_m, y_m)$을 $m$개 고른다. 각 쌍은 $1 \le x_i \le y_i \le n$을 만족해야 한다.
• 구간합은 다음과 같이 정의한다. $S(A, x, y) = \sum_{j=1}^{m} \left( \sum_{i=x_j}^{y_j} A[i] \right)$
• 목표는 $A$의 원소를 임의로 재배열하여 $S(A, x, y)$의 값을 최대로 만드는 것이다. 원소가 $n$개이므로 재배열은 총 $n!$가지이다.

예를 들어 $n = 3$, $m = 2$, $A = [10, 100, 1000]$, $x = [1, 2]$, $y = [2, 2]$이면 최댓값은 $2100$이고, 이 값은 $[100, 1000, 10]$으로 재배열했을 때만 얻어진다.

다른 예로 $n = 2$, $m = 1$, $A = [20, 22]$, $x = [1]$, $y = [2]$이면 최댓값은 $42$이고, 두 가지 재배열 모두 이 값을 달성한다.

$A$, $x$, $y$가 주어졌을 때 $A$의 원소를 재배열하여 얻을 수 있는 $S(A, x, y)$의 최댓값을 구하고, 그 최댓값을 달성하는 재배열이 몇 가지인지 구하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에 $n$과 $m$이 공백으로 구분되어 주어진다. 둘째 줄에는 배열 $A$의 원소 $n$개가 공백으로 구분되어 주어진다. 다음 $m$줄에는 각 줄마다 정수 $x_i$와 $y_i$가 공백으로 구분되어 주어진다.

각 테스트 케이스마다 $S(A, x, y)$의 최댓값과 그 최댓값을 달성하는 재배열의 수를 공백으로 구분하여 한 줄에 출력한다. 재배열의 수는 $10^9+7$로 나눈 나머지를 출력한다.

• $1 \le T \le 10$
• $1 \le n \le 50\,000$
• $1 \le m \le 200\,000$
• $A$의 각 원소는 $1$ 이상 $10^8$ 이하이다
• 배열 $A$의 원소는 모두 고유하다
• 모든 정수 $i$ ($1 \le i \le m$)에 대하여 $1 \le x_i \le y_i \le n$이다