BOI-handsome 수

자릿수가 1, 2, 3 세 종류뿐인 수를 생각한다. 특별한 집합 $F$ 는 두 자리의 순서쌍들을 원소로 가진다. 어떤 수에서 이웃한 두 자리로 이루어진 순서쌍 중 하나라도 $F$ 에 속하면, 그 수를 위험한 수라고 부른다.

수 $x$ 가 다음 세 조건을 모두 만족하면 BOI-handsome 수라고 한다.

• $x$ 는 오직 자릿수 1, 2, 3 으로만 이루어진다.
• $x$ 는 정확히 $n$ 자리이다.
• $x$ 는 위험한 수가 아니다.

BOI-handsome 수들을 비교하는 순서는 보통의 대소 비교와 다르다. 왼쪽에서부터 1번째, 2번째 자리 순서로 비교하는 대신, ${1, 2, \dots, n}$ 의 어떤 순열 $P$ 에 따라 비교한다. 즉 먼저 $P(1)$ 번째 자리를 비교하고, 같으면 $P(2)$ 번째 자리를, 그다음 $P(3)$ 번째 자리를 비교하며, $P(n)$ 번째 자리까지 이어간다. 이 비교 순서를 P-순서라고 부른다.

BOI-handsome 수 $B$ 가 주어질 때, P-순서로 $B$ 보다 작거나 같은 BOI-handsome 수가 몇 개인지 구하라. 답이 매우 커질 수 있으므로 $10^9 + 7$ 로 나눈 나머지를 출력한다.

첫째 줄에 BOI-handsome 수의 자릿수 $n$ 이 주어진다.

둘째 줄에 순열 $P$ 를 나타내는 $n$ 개의 정수가 공백으로 구분되어 주어진다. $i$ 번째 정수가 $P(i)$ 이다.

셋째 줄에 집합 $F$ 의 원소 개수 $m$ 이 주어진다.

넷째 줄에 $F$ 의 서로 다른 원소 $m$ 개가 공백으로 구분되어 주어진다. 각 원소는 두 자리 수 $ab$ 형태이다.

다섯째(마지막) 줄에 수 $B$ 가 주어진다.

P-순서로 $B$ 보다 작거나 같은 BOI-handsome 수의 개수를 $10^9 + 7$ 로 나눈 나머지를 한 줄에 출력한다.

• $1 < n \le 400,000$
• $1 \le m$
• $F$ 의 각 원소는 $a, b \in {1, 2, 3}$ 인 $ab$ 형태이다.
• $B$ 는 BOI-handsome 수이다.

아래는 첫 번째 예제($n = 3$, $P = (2, 1, 3)$, $F = {22, 13}$, $B = 321$)에 대한 설명이다.

자릿수 1, 2, 3 으로 이루어진 세 자리 수 중 P-순서로 $321$ 보다 작거나 같은 수를, P-순서로 증가하는 순으로 나열하면 다음과 같다.

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

이 가운데 $113, 213, 313, 122, 221, 222, 223$ 은 이웃한 두 자리에 $13$ 또는 $22$ 를 포함하므로 위험한 수이다. 남은 9 개가 BOI-handsome 수이므로 답은 $9$ 이다.