BOI-handsome Numbers

Consider numbers written using only the digits 1, 2, and 3. A special set $F$ contains ordered pairs of digits. A number is called dangerous if any ordered pair of its two consecutive digits belongs to $F$.

A number $x$ is a BOI-handsome number if all of the following hold:

• $x$ consists only of the digits 1, 2, and 3.
• $x$ has exactly $n$ digits.
• $x$ is not a dangerous number.

BOI-handsome numbers are not ordered in the usual way. Instead of comparing the digit in position 1 (from the left) first, then position 2, and so on, they are compared according to a permutation $P$ of ${1, 2, \dots, n}$. We first compare the digits in position $P(1)$; if they are equal we compare position $P(2)$, then $P(3)$, and so on up to position $P(n)$. Call this the P-ordering.

Given a BOI-handsome number $B$, count how many BOI-handsome numbers are smaller than or equal to $B$ in the P-ordering. Because the answer can be large, output it modulo $10^9 + 7$.

The first line contains a single integer $n$, the number of digits in the BOI-handsome numbers.

The second line contains $n$ space-separated integers describing the permutation $P$; the $i$-th integer is $P(i)$.

The third line contains a single integer $m$, the number of elements in the set $F$.

The fourth line contains the $m$ distinct members of $F$, separated by spaces. Each member is a two-digit string $ab$.

The fifth (last) line contains the number $B$.

Print, on a single line, the number of BOI-handsome numbers smaller than or equal to $B$ in the P-ordering, taken modulo $10^9 + 7$.

• $1 < n \le 400,000$
• $1 \le m$
• Each member of $F$ has the form $ab$ with $a, b \in {1, 2, 3}$.
• $B$ is a BOI-handsome number.

The following explains the first example ($n = 3$, $P = (2, 1, 3)$, $F = {22, 13}$, $B = 321$).

The three-digit strings over ${1, 2, 3}$ that are smaller than or equal to $321$ in the P-ordering, listed in increasing P-order, are:

$$111, 112, 113, 211, 212, 213, 311, 312, 313, 121, 122, 123, 221, 222, 223, 321$$

Of these, $113, 213, 313, 122, 221, 222, 223$ are dangerous because two of their consecutive digits form $13$ or $22$. The remaining 9 are BOI-handsome, so the answer is $9$.