P8062 [BalkanOI 2012] handsome

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

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}}$. Please output the number of handsome numbers that are $\le B$ under the permutation $p$, modulo $10^9+7$.

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 one line: the number of handsome numbers that are $\le B$ under the permutation $p$, modulo $10^9+7$.

#### 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