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

The first line contains two integers $m,d$ ( $1<=m<=2000$ , $0<=d<=9$ ) — the parameters from the problem statement.

The second line contains positive integer $a$ in decimal presentation (without leading zeroes).

The third line contains positive integer $b$ in decimal presentation (without leading zeroes).

It is guaranteed that $a<=b$ , the number of digits in $a$ and $b$ are the same and don't exceed $2000$ .

Print the only integer $a$ — the remainder after dividing by $10^{9}+7$ of the number of d-magic numbers in segment $[a,b]$ that are multiple of $m$ .