Intervals
An integer number is called good if it consists of good digits.
You are given n intervals [l[i], r[i]] 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 10^9 + 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: l[i] and r[i] (0 ≤ l[i] ≤ r[i] < 10^10).
Output
Print the number of ways modulo 10^9 + 7.