시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 17 5 5 31.250%

문제

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 (109 + 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.

  • 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.
  • In 20% of test cases, it will hold n ≤ 1 000.
  • In 50% of test cases the input permutations will be the identity permutation, i.e. P(i) = i for each 1 ≤ i ≤ n.
  • In 20% of test cases the input permutations will be drawn uniformly at random.

출력

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.

예제 입력

3
2 1 3
2
22 13
321

예제 출력

9

힌트

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.