Consider the decimal presentation of an integer. Let's call a number d-magic if digit d appears in decimal presentation of the number on even positions and nowhere else.
For example, the numbers 1727374, 17, 1 are 7-magic but 77, 7, 123, 34, 71 are not 7-magic. On the other hand the number 7 is 0-magic, 123 is 2-magic, 34 is 4-magic and 71 is 1-magic.
Find the number of d-magic numbers in the segment [a,b] that are multiple of m. Because the answer can be very huge you should only find its value modulo 109+7 (so you should find the remainder after dividing by 109+7).
Output
Print the only integer
a − the remainder after dividing by
109+7 of the number of
d-magic numbers in segment
[a,b] that are multiple of
m.
Note
The numbers from the answer of the first example are
16,
26,
36,
46,
56,
76,
86 and
96.
The numbers from the answer of the second example are
2,
4,
6 and
8.
The numbers from the answer of the third example are
1767,
2717,
5757,
6707,
8797 and
9747.