5249번 - BOI-handsome 다국어

Little Đurica is a member of Secret Poets society, which is well-known for its number-related beliefs. “Dangerous numbers" belief is considered to be the most important one. A number is "dangerous" if any ordered pair of its consecutive digits is a member of a special set F.

Little Đurica is so excited about numbers that he decided to introduce his own numbers, so-called BOI-handsome numbers. For a number x we say it is a BOI-handsome number if the following holds:

• x consists only of digits 1, 2, and 3
• x contains n digits exactly
• x is not a dangerous number

However, the ordering of BOI-handsome numbers is not the standard one. Instead of first comparing digits at position 1 (from left side), then at position 2 and so on, the numbers are compared according to some permutation P of {1, 2, ..., n}. Given P, we first compare digits at position P(1), then P(2) and so on until P(n). Let us call this P-ordering.

Little Đurica picks a BOI-handsome number B. Compute how many BOI-handsome numbers are smaller or equal than B in P-ordering. Since little Đurica does not like huge numbers, return the count by modulo 1000000007 (10⁹ + 7).

The first line of the input contains a single integer n denoting the number of digits in BOI-handsome numbers. The next line contains n space-separated integers representing a permutation P. The i-th integer of the line represents P(i).

The next line contains a single integer m denoting the number of elements in the special set F. The next line contains m space-separated distinct members of F.

The fifth (last) line contains a single integer representing the number B.

On the first and the only line of the output, print the number of BOI-handsome numbers smaller than or equal to B with respect to P-ordering. The count should be output by modulo 1000000007.

• 1 < n ≤ 400 000
• 1 ≤ m
• Each member of F is of the form ab where a, b are from {1, 2, 3}
• B is a BOI-handsome number.

The numbers between 111 and B, in strictly increasing order with respect to P-ordering, consisting only of digits 1, 2, and 3, are:

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

Numbers 113, 213, 313, 122, 221, 222, and 223 are dangerous, since all of them contain 22 or 13. The remaining numbers are BOI-handsome.