CF628D Magic Numbers

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 $ 10^{9}+7 $ (so you should find the remainder after dividing by $ 10^{9}+7 $ ).

N/A

N/A

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 $ .