시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 31 | 6 | 6 | 33.333% |
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:
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.
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.