18984번 - RMQ Similar Sequence 다국어

문제

Chiaki has a sequence $A=\{a_1,a_2,\dots,a_n\}$. Let $\mathbf{RMQ}(A, l, r)$ be the minimum $i$ ($l \le i \le r$) such that $a_i$ is the maximum value in $a_l, a_{l+1}, \dots, a_{r}$.

Two sequences $A$ and $B$ are called RMQ Similar, if they have the same length $n$ and for every 1ドル \le l \le r \le n,ドル $\mathbf{RMQ}(A, l, r) = \mathbf{RMQ}(B, l, r)$.

For a given the sequence $A=\{a_1,a_2,\dots,a_n\},ドル define the weight of a sequence $B=\{b_1,b_2,\dots,b_n\}$ be $\sum\limits_{i=1}^{n} b_i$ (i.e. the sum of all elements in $B$) if sequence $B$ and sequence $A$ are RMQ Similar, or 0ドル$ otherwise. If each element of $B$ is a real number chosen independently and uniformly at random between 0ドル$ and 1ドル,ドル find the expected weight of $B$.

입력

There are multiple test cases. The first line of input contains an integer $T,ドル indicating the number of test cases. For each test case:

The first line contains an integer $n$ (1ドル \le n \le 10^6$) -- the length of the sequence.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ (1ドル \le a_i \le n$) denoting the sequence.

It is guaranteed that the sum of all n does not exceed 3ドル \times 10^6$.

출력

For each test case, output the answer as a value of a rational number modulo 10ドル^9 + 7$.

Formally, it is guaranteed that under given constraints the probability is always a rational number $\frac{p}{q}$ ($p$ and $q$ are integer and coprime, $q$ is positive), such that $q$ is not divisible by 10ドル^9 + 7$. Output such integer a between 0ドル$ and 10ドル^9 + 6$ that $p - aq$ is divisible by 10ドル^9 + 7$.

제한

힌트