RMQ 유사 수열

Chiaki는 수열 $A=\{a_1,a_2,\dots,a_n\}$을 가지고 있다. $\mathbf{RMQ}(A, l, r)$을 $a_l, a_{l+1}, \dots, a_{r}$ 중 최댓값이 $a_i$인 최소 $i$ ($l \le i \le r$)로 정의하자.

두 수열 $A$와 $B$가 RMQ 유사라는 것은, 두 수열의 길이가 $n$으로 같고 모든 $1 \le l \le r \le n$에 대해 $\mathbf{RMQ}(A, l, r) = \mathbf{RMQ}(B, l, r)$이라는 뜻이다.

주어진 수열 $A=\{a_1,a_2,\dots,a_n\}$에 대해 수열 $B=\{b_1,b_2,\dots,b_n\}$의 가중치를 다음과 같이 정의하자. 수열 $B$와 수열 $A$가 RMQ 유사하면 $\sum\limits_{i=1}^{n} b_i$ (즉, $B$의 모든 원소의 합)이고, 그렇지 않으면 $0$이다. $B$의 각 원소가 $0$과 $1$ 사이에서 독립적으로 균등하게 무작위로 선택된 실수일 때, $B$의 기댓값을 구하여라.

여러 테스트 케이스가 주어진다. 입력의 첫 줄에는 테스트 케이스의 수를 나타내는 정수 $T$가 주어진다. 각 테스트 케이스는 다음과 같다.

첫 줄에는 정수 $n$ ($1 \le n \le 10^6$)이 주어진다. 이는 수열의 길이이다.

둘째 줄에는 수열을 나타내는 $n$개의 정수 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$)이 주어진다.

모든 $n$의 합은 $3 \times 10^6$을 넘지 않음이 보장된다.

각 테스트 케이스에 대해 답을 $10^9 + 7$로 나눈 나머지를 유리수 값으로 출력한다.

형식적으로, 주어진 제약 조건에서 확률은 항상 유리수 $\frac{p}{q}$ ($p$와 $q$는 정수이고 서로소이며 $q$는 양수)이고, $q$는 $10^9 + 7$로 나누어떨어지지 않음이 보장된다. $p - aq$가 $10^9 + 7$로 나누어떨어지는 $0$과 $10^9 + 6$ 사이의 정수 $a$를 출력한다.