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


-----Input-----

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.


-----Output-----

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.


-----Examples-----
Input
2 6
10
99

Output
8

Input
2 0
1
9

Output
4

Input
19 7
1000
9999

Output
6



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

Difficulty: interview

Starter code:

Solutions:
#!/usr/bin/env python3



def addmod(left, right, modulo=1000000007):
    res = left + right
    if res >= modulo:
        res -= modulo
    return res

def counter(a, m, d):
    res = [0, ] * (2*m)
    res[0] = 1
    shift = 1
    for pos in range(len(a), 0, -1):
        ptype = pos & 1
        cur = int(a[pos-1])
        tres = [0, ] * (2*m)
        for i in range(10):
            if ptype==1 and i == d:
                continue
            if ptype==0 and i != d:
                continue
            k = (i * shift) % m
            for j in range(m):
                k2 = k*2
                j2 = j*2
                if i < cur:
                    tres[k2+0] = addmod(tres[k2+0], addmod(res[j2+0], res[j2+1]))
                elif i == cur:
                    tres[k2+0] = addmod(tres[k2+0], res[j2+0])
                    tres[k2+1] = addmod(tres[k2+1], res[j2+1])
                else:
                    tres[k2+1] = addmod(tres[k2+1], addmod(res[j2+0], res[j2+1]))
                k = k+1 if k+1<m else 0
        res = tres
        shift = (shift * 10) % m
    return res[0]


def solver(ifs):
    m, d = list(map(int, ifs.readline().split()))
    a = ifs.readline().strip()
    b = ifs.readline().strip()
    res = counter(b, m, d)
    if a != '0':
        a = str(int(a) - 1)
        if len(a) < len(b):
            a = '0' + a
        modulo = 1000000007
        res = addmod(res, modulo - counter(a, m, d))
    print(res)

def main():
    import sys
    if sys.version_info.major == 3:
        from io import StringIO as StreamIO
    else:
         from io import BytesIO as StreamIO
    
    with StreamIO(sys.stdin.read()) as ifs, StreamIO() as ofs:
        _stdout = sys.stdout
        sys.stdout = ofs
        solver(ifs)
        sys.stdout = _stdout
        sys.stdout.write(ofs.getvalue())
    return 0

def __starting_point():
    main()

__starting_point()

import sys

m, d = list(map(int, input().split()))
mod = 10**9 + 7


def solve(a: list):
    dp = [0]*m
    border = a[0] % m if a[0] != d else -1
    m10 = 10 % m

    for i in range(a[0]):
        if i != d:
            dp[i % m] += 1

    for i, digit in enumerate(a[1:], start=1):
        next_dp = [0]*m

        if i & 1:
            t = d % m
            for j in range(m):
                next_dp[t] += dp[j]
                t = t + m10 if t + m10 < m else t + m10 - m

            if border != -1:
                if d < digit:
                    next_dp[(border * 10 + d) % m] += 1
                    border = -1
                elif d == digit:
                    border = (border * 10 + d) % m
                else:
                    border = -1
        else:
            for j in range(m):
                if dp[j] == 0:
                    continue
                if dp[j] >= mod:
                    dp[j] -= mod

                t = (j * 10 - 1) % m
                for k in range(10):
                    t += 1
                    if t == m:
                        t = 0
                    if k == d:
                        continue
                    next_dp[t] += dp[j]
                    if next_dp[t] >= mod:
                        next_dp[t] -= mod

            if border != -1:
                for k in range(digit):
                    if k == d:
                        continue
                    next_dp[(border * 10 + k) % m] += 1
                if digit != d:
                    border = (border * 10 + digit) % m
                else:
                    border = -1

        dp = next_dp

    return dp[0] + (1 if border == 0 else 0)


a = list(map(int, input()))
b = list(map(int, input()))
a[-1] -= 1

for i in range(len(a)-1, 0, -1):
    if a[i] < 0:
        a[i] = 9
        a[i-1] -= 1
    else:
        break

ans = solve(b) - solve(a)
print(ans % mod)