Problem Description

小 hua 发现了一个变幻莫测的图模型，边与边交织，图与图轮转。

小 hua 想知道在这个有向图中有多少条 $1$ 到 $n$ 的路径，结果对 $10^9+7$ 取模。

图由以下方式生成：

- 图共 $n$ 个节点，若干条边。
- 输入长度为 $n$ 的序列 $a_i$，每个 $a_i\in \{1, 2, \dots, c\}$。
- 再输入 $m$ 对**无序数对** $u,v$。（可以出现 $u=v$）
- 图上的节点 i, j 之间存在**有向边** i 到 j，当且仅当 **i 小于 j**，且 $a_i, a_j$ 出现在输入的 m 对**无序数对**中。

注意：无序数对代表，设 $m=1$ 且输入的是 $1,2$ 且 $a_1=2, a_2 = 1$，则图中是存在 $1\to 2$ 的边的。

Input

第一行一个正整数 $T$ 表示测试点个数。

对于每组数据：

第一行两个正整数 $n, c$，分别表示图的节点数和序列值域限制。

第二行 $n$ 个正整数，即数列 $a_i$。

第三行一个正整数 $m$。

后面 $m$ 行每行两个正整数 $u_i,v_i$，表示一个无序数对，保证每对无序数对不会重复出现。

Output

一个整数表示答案，对 $10^9+7$ 取模。

1
5 3
1 2 3 2 3
3
1 2
1 3
2 3

5

Hint

**本题输入量较大，请采用较快的输入方式。**

对于所有数据，$1\leq T\leq 5, 1\leq n,c\leq 10^5, 1\leq m\leq 2\times 10^5$，$1\leq a_i, u_i, v_i\leq c$。