题面描述

给定一个长度为 $n$ 的序列 $a$ 。同时给定 $m$ 个无序二元组 $(u,v)$ ，你需要求出有多少从序列的位置 $1$ 开始，到位置 $n$ 结束的路径，满足每次只能从 $i \to j(j>i)$ ，且 $a_i,a_j$ 出现在某个二元组中。

答案可能非常大，你只需要输出对 $10^9 + 7$ 取模后的结果。

再次提醒：二元组是无序的， $(u,v)$ 和 $(v,u)$ 是等价的， $u$ 可以等于 $v$ 。例如给定 $(1,2)$ ，那么 $a_i=2,a_j=1$ 是合法的。

输入格式

第一行两个正整数 $n, c$ ， $c$ 表示 $\max\{a\}$ 。

第二行 $n$ 个正整数表示序列 $a$ 。

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

接下来 $m$ 行每行两个正整数 $u,v$ 表示一个二元组。

输出一行一个整数表示答案。注意对 $10^9 + 7$ 取模。

对于 $100\%$ 的数据，满足 $n,c\le 10^5,m\le 2\times 10^5$ 。数据保证没有两个相同的二元组。

本题共 $100$ 个测试点。

对于测试点 $1\sim 8$ ，满足 $n,m\le 100$ 。

对于测试点 $9\sim 22$ ，满足 $n\le 5000$ 。

对于测试点 $23\sim 39$ ，满足 $c\le 1000$ 。

对于测试点 $40\sim 52$ ，满足 $a$ 是一个排列。