As we all know it's Rishabh's birthday and on this occasion his friend Viral wants to gift him something. BUT, being a GUJJU he doesn't want to spend any money so he decides to give him some special numbers. We will call a number x-gift if the digit x is present on only the even positions of the number and nowhere else.

Example: 1262527, 12 , 1 are 2-gift numbers but 22,2,176,44,21 are not 2-gift numbers .

2 is 0-gift, 173 is 7-gift , 24 is 4-gift, and 21 is 1-gift. Viral wants to gift him the maximum possible x-gift numbers in a given segment [l,r]. He finds out all the numbers and gifts them to Rishabh....BUT.. Rishabh rejected his gift and tells him to give only those numbers which are multiples of k. Viral tried a lot but he was unable to complete this job and he got so depressed that he is about to commit SUICIDE.

Can you guys save him. All you need to do is help him in finding the number of x-gift numbers in the segment [l,r] that are multiple of k. Print answer modulo 10^9 + 7 .

INPUT:

First line contains two integers k,x (1<=k<=2000, 0<=x<=9 )

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

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

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

OUTPUT: Print only one number — the remainder after dividing by 10^9 +7 of the number of x-gift numbers in segment [l,r] that are multiple of k.

Examples: sample input 1: 2 6 10 99 sample output 1: 8

sample input 2: 2 0 1 9 sample output 2: 4

sample input 3: 19 7 1000 9999 sample output 3: 6