Handsome Numbers

A positive integer with exactly N digits is defined as handsome if and only if:

1. Each digit is one of the set \(\{1,2,3\}\).
2. For every two consecutive digits (in the natural order), the ordered pair they form is not a dangerous pair.

In addition, you are given a permutation \(p\) of \(\{1,2,\dots,N\}\). The lexicographical order between two N-digit numbers \(X\) and \(Y\) with respect to permutation \(p\) is defined as follows:

• \(X\) is lexicographically smaller than \(Y\) (in the sense of permutation \(p\)) if and only if there exists an index \(k\) such that \(X_{p_1} = Y_{p_1}, X_{p_2} = Y_{p_2}, \dots, X_{p_{k-1}} = Y_{p_{k-1}}\) and \(X_{p_k} < Y_{p_k}\).
• \(X\) is equal to \(Y\) if \(X_{p_i} = Y_{p_i}\) for all \(1 \le i \le N\).
• \(X\) is lexicographically greater than \(Y\) if and only if there exists an index \(k\) such that \(X_{p_1} = Y_{p_1}, X_{p_2} = Y_{p_2}, \dots, X_{p_{k-1}} = Y_{p_{k-1}}\) and \(X_{p_k} > Y_{p_k}\).

You are given an N-digit number \(B\). Your task is to count the number of handsome numbers that are lexicographically less than or equal to \(B\) with respect to permutation \(p\). Since the answer can be very large, output it modulo \(10^9+7\).

Note on dangerous pairs: The dangerous pairs are specified in the input. A pair \((a,b)\) means that if two adjacent digits in the number (in natural order) are \(a\) followed by \(b\), then the number is not considered handsome.

inputFormat

The input begins with:

1. An integer \(N\) representing the number of digits.
2. A line with \(N\) integers, denoting a permutation \(p\) of \(\{1,2,\dots,N\}\). The permutation is 1-indexed.
3. An N-digit number \(B\) (as a string, possibly with leading digits) to compare against.
4. An integer \(M\) representing the number of dangerous pairs.
5. Then \(M\) lines follow. Each line contains two integers (each from the set \(\{1,2,3\}\)) which describe a dangerous ordered pair.

outputFormat

Output a single integer, the number of handsome numbers that are lexicographically less than or equal to \(B\) with respect to the permutation \(p\), modulo \(10^9+7\).

sample

2
1 2
33
1
1 1

8