题目背景

你是 OIer 中最帅的，所以你要做一道跟帅有关的题。

题目描述

一个 $N$ 位数是帅气的，当且仅当每一个数位上的数为 $1,2,3$ 中的一个。而且相邻的两个数位上的数字构成的有序数对不是“危险数对”。

• $N$ 位数 $X$ 在排列 $p$ 的意义下字典序小于 $N$ 位数 $Y$，当且仅当存在一个 $k$ 使得 $X_{p_1}=Y_{p_1},X_{p_2}=Y_{p_2},\dots,X_{p_{k}}<Y_{p_{k}}$。

• $N$ 位数 $X$ 在排列 $p$ 的意义下字典序等于 $N$ 位数 $Y$，当且仅当$X_{p_1}=Y_{p_1},X_{p_2}=Y_{p_2},\dots,X_{p_{N}}=Y_{p_{N}}$。

• $N$ 位数 $X$ 在排列 $p$ 的意义下字典序大于 $N$ 位数 $Y$，当且仅当存在一个 $k$ 使得 $X_{p_1}=Y_{p_1},X_{p_2}=Y_{p_2},\dots,X_{p_{k}}>Y_{p_{k}}$。

请你输出在排列 $p$ 意义下小于等于 $B$ 的帅气数的个数模 $10^9+7$ 的值。

输入格式

输入的第一行包含一个整数 $N$，表示数字位数。

第二行包含 $N$ 个空格分隔的整数，表示排列 $p$。该行的第 $i$ 个整数表示 $p_i$。

第三行包含一个整数 $M$，表示危险数对个数。

第四行 $M$ 个空格分隔的两位整数，第 $i$ 个两位整数 $\overline{a_ib_i}$ 表示 $(a_i,b_i)$ 为危险数对。

第五行一个正整数 $B$ 表示给定帅气数。

输出格式

输出一行，表示在排列 $p$ 意义下小于等于 $B$ 的帅气数个数模 $10^9+7$。

3
2 1 3
2
22 13
321

9

提示

数据范围：

Subtask#0 为样例。

$1\le N\le4\times10^5$，$M>0$，$a_i,b_i\in\{1,2,3\}$。

保证 $B$ 为帅气数。

样例解释：

$113,122,131,132,133,213,221,222,223,313,322$ 不是帅气数，因为出现了危险数对 $(2,2)$ 或 $(1,3)$。

所以，所有 $3$ 位帅气数为：$ 111,112,121,123, 211,212,231,232,233, 311,312,321,323,331,332,333$。

在排列 $2,1,3$ 意义下小于等于 $321$ 的帅气数有：$111,112,121,123,211,212,311,312,321$

如 $323$ 在排列 $2,1,3$ 意义下与 $321$ 比较（设 $323$ 为 $X$，$321$ 为 $Y$）：

• 先比较第 $2$ 位：$X_2=Y_2=2$；
• 再比较第 $1$ 位：$X_1=Y_1=3$；
• 最后比较第 $3$ 位：$X_3=3>Y_3=1$。

所以 $323$ 在排列 $2,1,3$ 意义下大于 $321$，不是满足条件的帅气数。