Cartesian Trees

Recently, at a university lecture, Vasya learned what a Cartesian tree is. A Cartesian tree is a binary tree where each node stores two values: a key and a priority. It is a search tree over the set of keys and a max-heap over the priorities, that is:

• the key of any node in the left subtree of node $v$ is less than the key of node $v$;
• the key of any node in the right subtree of node $v$ is greater than the key of node $v$;
• the priorities of the children of node $v$ are not greater than the priority of node $v$ itself.

On a test, Vasya was given the following problem: given $n$ pairs of the form (key, value), the $i$-th of which is $(i, y_i)$, find how many ways there are to build a Cartesian tree using the number $i$ as the key of node $i$ and $y_i$ as its priority. Since this number can be quite large, find its remainder modulo $10^9+7$.

Two Cartesian trees are considered different if they have different roots, or if there is a node that has different ancestors in these trees.

The first line contains a single positive integer $t$: the number of test cases in the input. The descriptions of the test cases follow.

The description of each test case consists of two lines. The first line contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$): the number of nodes in the tree. The second line contains $n$ integers $y_i$ ($1 \le y_i \le 10^9$): the priority of the $i$-th node of the tree.

The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

For each test case, output on a separate line a single integer: the number of distinct Cartesian trees that can be built on the given set of priorities, modulo $10^9+7$.