You all heard about the Penguins of Madagaskar. They work for the penguin kind and loves cuteness. Octopus Dave has attacked all the penguins around the world. Dave captured all the penguins and put them into a laboratory except Rico, Skipper, Kowalski, and Private. The laboratory is protected from the outside world so that no-one can save the penguins.
Rico, Skipper, Kowalski, and Private formed a special team that will be deployed into operation to save other penguins from Dave. The first step to getting into the laboratory is to hack the secured entry system. In this system, one needs to solve a problem asked by the computerized security system to get into the lab. Private solved the problem and made the operation easier for Rico, Skipper, Kowalski. Can you solve the problem?
In this problem, we shall work with 105 based number system.
In 105 based number system digits are in the range [0 , 99999]. Note that here, 99999 is considered as a single digit. An example in 105 based number system is:
N = (152)(163)(9)(9998)
Here 152, 163,9,9998 all are single digits. We used parenthesis to distinguish each digit from others. Here, The leftmost digit is 152 which is also the most significant digit of this number. The rightmost digit is 9998 which is the least significant digit of the number.
You will be given a list of integers L which is a list of beauty digits. After that, you will be given multiple queries. Each query contains two numbers A and B in 105 based number system. You have to calculate F(A , B). The function F(A,B) calculates beautiful numbers in the range [A , B] inclusive. Definition of Beautiful Numbers is given below:
"Numbers which contains each beauty digit from the list of beauty L even number of times as their digits are called Beautiful Numbers".
In 105 based number system, the digits of the integers are in range [ 0 , 99999 ]. We shall give you the digits of the number A, separated by spaces to make things easier for you. Then we shall give you the digits of the number B, separated by spaces to make things easier for you
for example, the list L contains the integers 1 , 2 , 3 and A = 1 , B = 16.
You have 13 beautiful numbers in the range [A,B].
Since the result may be large , print result modulo 1000000007.
The first line of the input will contain an integer Z, the size of the beauty list. There will be Z integers in the next line.
After that, there will be an integer Q, the number of queries followed by Q queries. Each query will start with two integers X, Y.
X, Y denotes the number of digits of the numbers A and B respectively. Then, there will be two lines of input. The first line contains X integers which are digits of number A. The second line contains Y integers which are digits of the number B.
For 30 points:
A,B will be within the range [ (1)(1) , (50)(99999)]
For 100 points:
All the beauty values, digits of A and B are in the range [1,99999]. That means in A and B will not contain any digit which is 0. But the numbers you will make between A and B may contain 0.
It is guaranteed that A<=B and Numbers doesn't contain leading zeros.
For each query output "Case x: y" without quotations where x denotes the xth query and y is the answer to the query. See sample output for better understanding.
1 9 4 1 1 1 1 2 5 63 12 125 1 8 6 93 1 1 1 100 1 1 50 120
Case 1: 1 Case 2: 234105042 Case 3: 99 Case 4: 71