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<sup class="upper-index">9</sup> + 7 (so you should find the remainder after dividing by 10<sup class="upper-index">9</sup> + 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.
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.
2 6
10
99
8
2 0
1
9
4
19 7
1000
9999
6
9 4
33
52
0
10 8
18
59
0
43 3
587
850
1
65 3
3436
3632
0
850 8
55735
94089
0
590 6
428671
715453
0
1053 8
1539368
3362621
0
477 9
3062053
6465858
6
1901 9
1941695
3314270
0
29 0
1649127
6241670
126
566 3
6372451659957700362854162843720623142601337360014410221724168092176479911659703538545016668832338549
7969973326176891147525183958122002014921396842270051000646823226374743898663307171214245111949604186
0
1286 5
1886373541983002858974907276497223649072414883083336663541044958378875954171855070620868427474284001
4050983123791059817478363830631049287126338893626273758612677264947268375965600848751800494833017145
0
2 5
1762712
8121765
2025
2 2
12
12
1
2 0
10
10
1
2 6
46
46
1
2 0
10
20
2
2 9
10000000000
99999999999
262440
10 2
12300
99900
70
5 5
5
5
0
1 2
113548484131315415454546546467913135484841313154154
895458414564646646487131313118761454584145646466464
970729981
2 2
12
14
1
2 2
2934
4323
18
2 4
1
9
3
1 0
10
20
2
7 7
7
7
0
2 1
143
413
12
1 4
1
9
8
2 6
36
36
1
4 4
24344
48880
29
2 0
1000
9999
81
3 9
39
39
1
3 9
10
99
2
1 0
10000
99999
729
3 2
681563
828242
48
1 5
454
667
14
2 0
2
9
4
2 6
7
9
1
10 7
1
1
0
6 0
1
6
1
6 2
22
95
2
28 1
102
898
2
1 0
1
9
9
1 1
1
9
8
3 9
10
69
2
1 0
1
1
1
from sys import *
from collections import defaultdict as dd
setrecursionlimit(10**6+999);MOD=int(1e9)+7
input=stdin.readline;TC=1
def is_A_d_magic_number(a):
    if(int(a)%m):return 0
    for i in range(0,len(a)):
        if(i%2==0 and int(a[i])==d):return 0
        if(i%2!=0 and int(a[i])!=d):return 0
    return 1
def solve(pos,tight,mod,st,even):
    if(pos==len(s)):
        return mod==0
    if(dp[pos,tight,mod,st,even]!=-1):
        return dp[pos,tight,mod,st,even]
    ret=0
    end=(int(s[pos]) if(tight) else 9)
    if(st==0):
        tight1=(tight&(s[pos]=='0'))
        ret=ret+solve(pos+1,tight1,mod,st,0)%MOD
        for i in range(1,end+1):
            if(i!=d):
                mod1=(mod*10+i)%m
                tight1=(tight&(i==end))
                ret=ret+solve(pos+1,tight1,mod1,1,1)%MOD
    else:
        for i in range(0,end+1):
            mod1=(mod*10+i)%m
            tight1=(tight&(i==end))
            if((even and i==d) or ((not even) and i!=d)):
                ret=ret+solve(pos+1,tight1,mod1,1,even^1)%MOD
    dp[pos,tight,mod,st,even]=ret
    return dp[pos,tight,mod,st,even]
if __name__=='__main__':
    for tc in range(TC):
        m,d=map(int,input().split())
        a,b=input().split()[0],input().split()[0]
        if(1):
            s=b
            dp=dd(lambda:-1)
            ans=solve(0,1,0,0,0)%MOD
        if(1):
            s=a
            dp=dd(lambda:-1)
            ans=((ans-solve(0,1,0,0,0))+MOD)%MOD
        print(ans + is_A_d_magic_number(a))
