배열 구간합 놀이

Alice는 정수 배열을 이용한 구간합 놀이를 즐겨하는데, 아래와 같은 순서로 게임을 진행한다.

• 먼저, 길이 $n$인 정수 배열 $A$를 만든다. $A$의 원소가 $A\[1]$, $\dots$, $A\[n]$이라 했을 때 이 $n$개의 값은 모두 달라야 한다.
• 다음으로, 배열 $A$의 구간을 나타내는 $m$개의 정수 쌍 $(x\[1], y\[1])$, $\dots$, $(x\[m], y\[m])$을 고른다. 이 때 $1 ≤ x\[i] ≤ y\[i] ≤ n$ 을 만족해야한다.
• 배열 $A$와 $x$, $y$를 이용하여 구간합 $S(A, x, y)$을 다음과 같이 정의한다: $S(A, x, y) := \sum\_{1 \le j \le m} ( \sum\_{x\[j] \le i \le y\[j]} A\[i] )$
• 이 게임의 목표는 배열 $A$의 원소를 임의로 재배열하여 $S(A, x, y)$값을 최대로 만드는 것이다. $A$의 원소가 $n$개이므로 총 $n!$ 가지의 방법으로 $A$의 원소를 재배열할 수 있다.

예를 들어, $n = 3$, $m = 2$, $A = \[10, 100, 1000]$ 이고 $x = \[1, 2]$, $y = \[2, 2]$라 하자. $n = 3$ 이므로 $A$의 원소를 재배열하여 얻을 수 있는 배열은 총 여섯 종류가 있다. 원래의 배열 $A$와 구분하기 위해 이를 배열 $B$라 하자.

• $B = \[10, 100, 1000]$ 일 때, $S(B, x, y) = (10 + 100) + (100) = 210$.
• $B = \[10, 1000, 100]$ 일 때, $S(B, x, y) = (10 + 1000) + (1000) = 2010$.
• $B = \[100, 10, 1000]$ 일 때, $S(B, x, y) = (100 + 10) + (10) = 120$.
• $B = \[100, 1000, 10]$ 일 때, $S(B, x, y) = (100 + 1000) + (1000) = 2100$.
• $B = \[1000, 10, 100]$ 일 때, $S(B, x, y) = (1000 + 10) + (10) = 1020$.
• $B = \[1000, 100, 10]$ 일 때, $S(B, x, y) = (1000 + 100) + (100) = 1200$.

이 경우 $S(A, x, y)$의 최댓값은 $2100$이며, 네 번째 경우인 $B = \[100, 1000, 10]$를 통해 얻을 수 있다.

다른 예로, $n = 2$, $m = 1$, $A = \[20, 22]$ 이고 $x = \[1]$, $y = \[2]$라 하자. $n = 2$ 이므로 $A$의 원소를 재배열하여 얻을 수 있는 배열은 총 두 종류가 있다. 원래의 배열 $A$와 구분하기 위해 이를 배열 $B$라 하자.

• $B = \[20, 22]$ 일 때, $S(B, x, y) = (20 + 22) = 42$.
• $B = \[22, 20]$ 일 때, $S(B, x, y) = (22 + 20) = 42$.

이 경우 $S(A, x, y)$의 최댓값은 $42$이며, 두 가지 다른 방법을 통해 얻을 수 있다.

$A$, $x$, $y$가 주어졌을 때 Alice가 $A$의 원소를 재배열하여 달성할 수 있는 $S(A, x, y)$의 최댓값을 구하고, 몇 가지 다른 방법으로 최댓값을 달성할 수 있는지 구해보자.

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

각 테스트 케이스의 입력 첫 줄에 $n$, $m$이 공백으로 구분되어 주어진다. 둘째 줄에는 배열 $A$의 원소 $n$개가 공백으로 구분되어 주어진다. 다음 $m$줄에 걸쳐 각 줄에 두 개의 정수 $x\[i]$와 $y\[i]$가 공백으로 구분되어 주어진다.

각 테스트 케이스의 정답인 Alice가 달성할 수 있는 $S(A, x, y)$의 최댓값, 그리고 이를 달성할 수 있는 방법의 수를 공백으로 구분하여 출력한다. 단, 방법의 수가 매우 커질 수 있으므로 $10^9+7$로 나눈 나머지를 출력한다.

• $1 ≤ T ≤ 10$
• $1 ≤ n ≤ 50\\,000$
• $1 ≤ m ≤ 200\\,000$
• $1 ≤ A$의 원소 $≤ 10^8$
• 배열 $A$의 원소는 고유하다
• $1 ≤ i ≤ m$인 정수 $i$에 대하여 $1 ≤ x\[i] ≤ y\[i] ≤ n$