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: HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
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)


import os, sys
from io import BytesIO, IOBase
from array import array

def solve(x, m, d, mod, par):
	dp = [[array('i', [0]) * m for _ in range(2)] for _ in range(len(x))]
	zz = int(x[0])
	for _ in range(1, zz):
		if _ == d:
			continue
		dp[0][0][_ % m] += 1
	if zz != d:
		dp[0][1][zz % m] = 1
	for i in range(1, len(x)):
		zz = int(x[i])
		if i & 1:
			for j in range(m):
				z = (j * 10 + d) % m
				dp[i][0][z] = (dp[i][0][z] + dp[i - 1][0][j] + (0 if d >= zz else dp[i - 1][1][j])) % mod
				dp[i][1][z] = (dp[i][1][z] + (0 if d != zz else dp[i - 1][1][j])) % mod
		else:
			for j in range(m):
				for k in range(10):
					if k == d:
						continue
					z = (j * 10 + k) % m
					dp[i][0][z] = (dp[i][0][z] + dp[i - 1][0][j] + (0 if k >= zz else dp[i - 1][1][j])) % mod
					dp[i][1][z] = (dp[i][1][z] + (0 if k != zz else dp[i - 1][1][j])) % mod
	if par:
		return (dp[len(x) - 1][0][0] + dp[len(x) - 1][1][0]) % mod
	return dp[len(x) - 1][0][0]

def main():
	(m, d) = map(int, input().split())
	a = input().strip()
	b = input().strip()
	print((solve(b, m, d, 10 ** 9 + 7, 1) - solve(a, m, d, 10 ** 9 + 7, 0)) % (10 ** 9 + 7))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


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