In the silent town of Iberia, Gran Faro, the afterglow of the golden age has long been covered by gray clouds. The spreading "Abyssal Scourge" is like a living creature that breathes, slowly devouring the remaining streets of the town.

To open a path to the coast, Little H has entrusted Rhodes Island operator Kaka to clean up the Abyssal Scourge on the town's main road. This main road can be viewed as a number line with $n$ blocks to be cleaned, numbered $1, 2, \dots, n$ by position. Due to varying degrees of deep-sea erosion, the concentration of the Abyssal Scourge in the $i$-th block is $p_i$ ($1 \le p_i \le W$).

The engineering department has urgently deployed a cleaning machine modified from a former Iberian monastery attendant—the "Little Helper." Kaka needs to operate the "Little Helper" to perform $m$ cleaning operations. The $i$-th operation can be represented as a triple $(op_i, x_i, w_i)$, where $w_i$ is the cleaning power set for this operation ($1 \le w_i \le W$):

• If $op_i = 0$, the "Little Helper" advances from the left side of the main road, cleaning all blocks $j$ that satisfy $1 \le j \le x_i$ and $p_j < w_i$;
• If $op_i = 1$, the "Little Helper" advances from the right side of the main road, cleaning all blocks $j$ that satisfy $x_i \le j \le n$ and $p_j < w_i$.

Given the concentrations $p_i$ of all blocks and the direction $op_i$ and range $x_i$ for each operation, how many ways are there to set the cleaning powers $(w_1, w_2, \dots, w_m)$ such that every block is successfully cleaned at least once?

Output the number of valid schemes modulo $10^9 + 7$. Two schemes are considered different if and only if there exists at least one $i \in \{1, 2, \dots, m\}$ such that the cleaning power $w_i$ set in these two schemes is different.

Input

This problem contains multiple test cases.

The first line contains a single positive integer $T$ ($1 \le T \le 5 \times 10^3$) representing the number of test cases. For each test case:

The first line contains three positive integers $n, m, W$ ($1 \le n, W \le 5 \times 10^3$, $1 \le m \le 10^6$) representing the number of blocks, the number of cleaning operations, and the upper bound of the Abyssal Scourge concentration, respectively.

The second line contains $n$ positive integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le W$) representing the concentration of the Abyssal Scourge in each block.

The next $m$ lines each contain two positive integers $op_i, x_i$ ($op_i \in \{0, 1\}$, $1 \le x_i \le n$) representing the parameters of the $i$-th cleaning operation.

It is guaranteed that the sum of $n$ over all test cases does not exceed $5 \times 10^3$, and the sum of $m$ over all test cases does not exceed $10^6$.

Output

For each test case, output a single integer on a new line representing the number of power setting schemes such that "all blocks are cleaned at least once," modulo $10^9 + 7$.

Examples

Input 1

2
3 3 3
1 2 1
1 1
1 2
0 3
5 5 6
5 1 4 2 3
0 4
0 2
0 1
1 3
0 5

Output 1

18
2897