Background

You are the most handsome among OIers, so you have to solve a problem related to being handsome.

Problem Description

An $N$-digit number is handsome if and only if every digit is one of $1,2,3$. Also, the ordered pair formed by any two adjacent digits is not a “dangerous pair”.

• An $N$-digit number $X$ is lexicographically smaller than an $N$-digit number $Y$ under the permutation $p$ if and only if there exists a $k$ such that $X_{p_1}=Y_{p_1},X_{p_2}=Y_{p_2},\dots,X_{p_{k}}<Y_{p_{k}}$.

• An $N$-digit number $X$ is lexicographically equal to an $N$-digit number $Y$ under the permutation $p$ if and only if $X_{p_1}=Y_{p_1},X_{p_2}=Y_{p_2},\dots,X_{p_{N}}=Y_{p_{N}}$.

• An $N$-digit number $X$ is lexicographically greater than an $N$-digit number $Y$ under the permutation $p$ if and only if there exists a $k$ such that $X_{p_1}=Y_{p_1},X_{p_2}=Y_{p_2},\dots,X_{p_{k}}>Y_{p_{k}}$.

Please output the number of handsome numbers that are $\le B$ under the permutation $p$, modulo $10^9+7$.

Input Format

The first line contains an integer $N$, the number of digits.

The second line contains $N$ space-separated integers, representing the permutation $p$. The $i$-th integer on this line is $p_i$.

The third line contains an integer $M$, the number of dangerous pairs.

The fourth line contains $M$ space-separated two-digit integers. The $i$-th two-digit integer $\overline{a_ib_i}$ indicates that $(a_i,b_i)$ is a dangerous pair.

The fifth line contains a positive integer $B$, the given handsome number.

Output Format

Output one line: the number of handsome numbers that are $\le B$ under the permutation $p$, modulo $10^9+7$.

3
2 1 3
2
22 13
321

9

Hint

Constraints

Subtask#0 is the sample.

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

It is guaranteed that $B$ is a handsome number.

Sample Explanation

$113,122,131,132,133,213,221,222,223,313,322$ are not handsome numbers, because the dangerous pair $(2,2)$ or $(1,3)$ appears.

So, all handsome $3$-digit numbers are: $111,112,121,123, 211,212,231,232,233, 311,312,321,323,331,332,333$.

Under the permutation $2,1,3$, the handsome numbers that are $\le 321$ are: $111,112,121,123,211,212,311,312,321$.

For example, compare $323$ and $321$ under the permutation $2,1,3$ (let $323$ be $X$ and $321$ be $Y$):

• First compare the $2$-nd digit: $X_2=Y_2=2$.
• Then compare the $1$-st digit: $X_1=Y_1=3$.
• Finally compare the $3$-rd digit: $X_3=3>Y_3=1$.

So $323$ is greater than $321$ under the permutation $2,1,3$, and it is not a valid handsome number.

Translated by ChatGPT 5