An integer number is called good if it consists of good digits.

You are given n intervals [li, ri] and the set of digits which are considered good. Find how many ways there are to choose one integer from each of those intervals so that their sum will be a good number. You can choose the same number in multiple intervals. Two ways are considered different if there exists an integer i (1 ≤ i ≤ n) such that different integers are chosen from interval i. The answer may be large, so you have to give it modulo 109 + 7.

Input

The first line contains ten integers: i-th of them is equal to 1 if digit i is good and 0 otherwise. These integers are numbered from 0 to 9. The next line contains a single integer n (1 ≤ n ≤ 7): the number of intervals. Next n lines contain two integers each without leading zeros: li and ri (0 ≤ li ≤ ri < 1010).

Output

Print the number of ways modulo 109 + 7.