题目描述

给你 $4$ 个数 $m,d,l,r$ ,保证 $l,r$ 位数相同。问满足以下条件的数 $x$ 的个数：

1. $l \leq x\leq r$；
2. $x$ 的偶数位是 $d$，奇数位不是 $d$，这里定义偶数位为从高位往低位的数的偶数位；
3. $m|x$。

答案对 $10^9+7$ 取模。

输入格式

第一行两个整数 $m,d$，$1\le m\le 2000$，$0\le d\le 9$。

第二行一个整数 $l$，第三行一个整数 $r$，$1\le l\le r\le 10^{2000}$。

输出格式

输出一个整数表示答案，对 $10^9+7$ 取模。

2 6
10
99

8

2 0
1
9

4

19 7
1000
9999

6