#include <bits/stdc++.h>
using namespace std;
class IO {
  static const int bufSize = 1 << 18;
  char inBuf[bufSize], outBuf[bufSize];
  char *ip1 = inBuf, *ip2 = inBuf;
  int ok = 1, op1 = -1, op2 = bufSize - 1;
  template <typename T>
  __inline__ __attribute__((always_inline)) void __RI(T &x) {
    int ch = gc(), neg = 1;
    x = 0;
    for (; !(ch == EOF || isdigit(ch) || ch == '-'); ch = gc())
      ;
    if (ch == EOF) {
      ok = 0;
      return;
    }
    if (ch == '-') neg = -1, ch = gc();
    for (; isdigit(ch); ch = gc()) x = x * 10 + (ch - 48) * neg;
  }
  template <typename T>
  __inline__ __attribute__((always_inline)) void __RC(T &x) {
    unsigned char ch;
    while (isspace(ch = gc()))
      ;
    if (ch == EOF) {
      ok = 0;
      return;
    }
    x = ch;
  }
  __inline__ __attribute__((always_inline)) void __RS(string &x) {
    char ch;
    x.clear();
    for (ch = gc(); isspace(ch); ch = gc())
      ;
    if (ch == EOF) {
      ok = 0;
      return;
    }
    for (; !isspace(ch); ch = gc()) x.push_back(ch);
  }

 public:
  __inline__ __attribute__((always_inline)) int gc() {
    return ip1 == ip2 && (ip2 = (ip1 = inBuf) + fread(inBuf, 1, bufSize, stdin),
                          ip1 == ip2)
               ? EOF
               : *ip1++;
  }
  __inline__ __attribute__((always_inline)) IO &R(char &x) {
    __RC(x);
    return *this;
  }
  __inline__ __attribute__((always_inline)) IO &R(unsigned char &x) {
    __RC(x);
    return *this;
  }
  __inline__ __attribute__((always_inline)) IO &R(string &x) {
    __RS(x);
    return *this;
  }
  template <typename T1, typename T2>
  __inline__ __attribute__((always_inline)) IO &R(pair<T1, T2> &x) {
    R(x.first), R(x.second);
    return *this;
  }
  template <typename T>
  __inline__ __attribute__((always_inline)) IO &R(vector<T> &x) {
    for (auto &i : x) R(i);
    return *this;
  }
  template <typename T, typename... Args>
  __inline__ __attribute__((always_inline)) IO &RA(T *a, int n) {
    for (int i = 0; i < n; ++i) R(a[i]);
    return *this;
  }
  template <typename T, typename... Args>
  __inline__ __attribute__((always_inline)) IO &R(T &x, Args &...args) {
    R(x), R(args...);
    return *this;
  }
  template <typename T, typename... Args>
  __inline__ __attribute__((always_inline)) IO &RA(T *a, int n, Args... args) {
    for (int i = 0; i < n; ++i) RA(a[i], args...);
    return *this;
  }
  template <typename T>
  __inline__ __attribute__((always_inline)) IO &R(T &x) {
    static_assert(is_integral<T>::value, "Unsupported types");
    if (is_integral<T>::value) __RI(x);
    return *this;
  }

 private:
  char space = ' ';
  template <typename T>
  __inline__ __attribute__((always_inline)) void __WI(T x) {
    static char buf[64];
    static int len = -1;
    if (x >= 0) {
      do {
        buf[++len] = x % 10 + 48, x /= 10;
      } while (x);
    } else {
      pc('-');
      do {
        buf[++len] = -(x % 10) + 48, x /= 10;
      } while (x);
    }
    while (len >= 0) {
      pc(buf[len]), --len;
    }
  }

 public:
  __inline__ __attribute__((always_inline)) void pc(const char &x) {
    if (op1 == op2) flush();
    outBuf[++op1] = x;
  }
  __inline__ __attribute__((always_inline)) void flush() {
    fwrite(outBuf, 1, op1 + 1, stdout), op1 = -1;
  }
  __inline__ __attribute__((always_inline)) IO &W(const char &x) {
    pc(x);
    return *this;
  }
  __inline__ __attribute__((always_inline)) IO &W(const char *x) {
    while (*x != '\0') pc(*(x++));
    return *this;
  }
  __inline__ __attribute__((always_inline)) IO &W(const string &x) {
    W(x.c_str());
    return *this;
  }
  template <typename T>
  __inline__ __attribute__((always_inline)) IO &W(const vector<T> &x) {
    for (auto &i : x) WS(i);
    WL();
    return *this;
  }
  __inline__ __attribute__((always_inline)) IO &WL() {
    W('\n');
    return *this;
  }
  template <typename T1, typename T2>
  __inline__ __attribute__((always_inline)) IO &W(const pair<T1, T2> &x) {
    WS(x.first), W(x.second);
    return *this;
  }
  template <typename T>
  __inline__ __attribute__((always_inline)) IO &WL(const T &x) {
    W(x), W('\n');
    return *this;
  }
  __inline__ __attribute__((always_inline)) IO &WS() {
    W(space);
    return *this;
  }
  template <typename T>
  __inline__ __attribute__((always_inline)) IO &WS(const T &x) {
    W(x), W(space);
    return *this;
  }
  template <typename T>
  __inline__ __attribute__((always_inline)) IO &WA(T *a, int n) {
    for (int i = 0; i < n; i++) WS(a[i]);
    WL();
    return *this;
  }
  template <typename T, typename... Args>
  __inline__ __attribute__((always_inline)) IO &W(const T &x,
                                                  const Args &...args) {
    W(x), W(space), W(args...);
    return *this;
  }
  template <typename... Args>
  __inline__ __attribute__((always_inline)) IO &WS(const Args &...args) {
    W(args...), W(space);
    return *this;
  }
  template <typename... Args>
  __inline__ __attribute__((always_inline)) IO &WL(const Args &...args) {
    W(args...), W('\n');
    return *this;
  }
  template <typename T, typename... Args>
  __inline__ __attribute__((always_inline)) IO &WA(T *a, int n, Args... args) {
    for (int i = 0; i < n; i++) WA(a[i], args...);
    return *this;
  }
  template <typename T>
  __inline__ __attribute__((always_inline)) IO &W(const T &x) {
    static_assert(is_integral<T>::value, "Unsupported types");
    if (is_integral<T>::value) __WI(x);
    return *this;
  }
  template <typename T>
  __inline__ __attribute__((always_inline)) IO &operator>>(T &x) {
    R(x);
    return *this;
  }
  template <typename T>
  __inline__ __attribute__((always_inline)) IO &operator<<(const T &x) {
    W(x);
    return *this;
  }
  bool good() { return ok; }
  IO() {}
  ~IO() { flush(); }
} io;
const int32_t INF = 0x3f3f3f3f;
const int64_t INFL = 0x3f3f3f3f3f3f3f3fLL;
const int MOD = 1e9 + 7;
namespace Math {
template <typename T, typename T2>
inline T qpow(T a, T2 b) {
  T ans = 1;
  for (; b; b >>= 1) {
    if (b & 1) ans = (a * ans) % MOD;
    a = (a * a) % MOD;
  }
  return ans;
}
template <typename T>
inline T exgcd(T l, T r, T &x, T &y) {
  if (!r) {
    x = 1, y = 0;
    return l;
  } else {
    int d = exgcd(r, l % r, y, x);
    y -= l / r * x;
    return d;
  }
}
template <typename T>
inline T inv(T a) {
  return qpow(a, MOD - 2);
}
template <typename T>
inline T exinv(T a) {
  T x, y;
  exgcd(a, MOD, x, y);
  x %= MOD;
  return x + ((x >> (sizeof(T) * 8 - 1)) & MOD);
}
template <typename T, T MOD>
struct ModInt {
  T x;
  ModInt(T x = 0) : x(x) {
    while (x < 0) x += MOD;
  }
  ModInt<T, MOD> operator+=(const ModInt<T, MOD> &y) {
    x += y.x - MOD;
    x += (x >> (sizeof(T) * 8 - 1)) & MOD;
    return (*this);
  }
  ModInt<T, MOD> operator-=(const ModInt<T, MOD> &y) {
    x = x - y.x;
    x += (x >> (sizeof(T) * 8 - 1)) & MOD;
    return (*this);
  }
  ModInt<T, MOD> operator*=(const ModInt<T, MOD> &y) {
    x = x * y.x % MOD;
    return (*this);
  }
  ModInt<T, MOD> operator/=(const ModInt<T, MOD> &y) {
    x = x * inv(y.x) % MOD;
    return (*this);
  }
};
template <typename T, T MOD>
ModInt<T, MOD> operator+(ModInt<T, MOD> a, const ModInt<T, MOD> &b) {
  a += b;
  return a;
}
template <typename T, T MOD>
ModInt<T, MOD> operator-(ModInt<T, MOD> a, const ModInt<T, MOD> &b) {
  a -= b;
  return a;
}
template <typename T, T MOD>
ModInt<T, MOD> operator*(ModInt<T, MOD> a, const ModInt<T, MOD> &b) {
  a *= b;
  return a;
}
template <typename T, T MOD>
ModInt<T, MOD> operator/(ModInt<T, MOD> a, const ModInt<T, MOD> &b) {
  a /= b;
  return a;
}
template <typename T, T MOD>
ModInt<T, MOD> operator+(ModInt<T, MOD> a, const T &b) {
  a += ModInt<T, MOD>(b);
  return a;
}
template <typename T, T MOD>
ModInt<T, MOD> operator-(ModInt<T, MOD> a, const T &b) {
  a -= ModInt<T, MOD>(b);
  return a;
}
template <typename T, T MOD>
ModInt<T, MOD> operator*(ModInt<T, MOD> a, const T &b) {
  a *= ModInt<T, MOD>(b);
  return a;
}
template <typename T, T MOD>
ModInt<T, MOD> operator/(ModInt<T, MOD> a, const T &b) {
  a /= ModInt<T, MOD>(b);
  return a;
}
}  // namespace Math
const int MAXN = 3000;
Math::ModInt<int, MOD> dp[MAXN][MAXN][2];
int m, d;
Math::ModInt<int, MOD> solve(string s) {
  memset(dp, 0, sizeof(dp));
  dp[0][0][1] = 1;
  int n = s.size();
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      for (int k = 0; k < 2; k++)
        if (i & 1) {
          if (k == 1 && s[i] < '0' + d) continue;
          auto cur = dp[i][j][k];
          auto &nxt = dp[i + 1][(j * 10 + d) % m][k & (s[i] == '0' + d)];
          nxt += cur;
        } else
          for (int t = 0; t < 10; t++) {
            if (t == d) continue;
            if (k == 1 && s[i] < '0' + t) continue;
            auto cur = dp[i][j][k];
            auto &nxt = dp[i + 1][(j * 10 + t) % m][k & (s[i] == '0' + t)];
            nxt += cur;
          }
    }
  }
  Math::ModInt<int, MOD> ans = 0;
  for (int k = 0; k < 2; k++) ans += dp[n][0][k];
  return ans;
}
Math::ModInt<int, MOD> good(string s) {
  int r = 0;
  for (int i = 0; i < s.size(); i++) {
    if ((i & 1) ^ (s[i] == d + '0')) return 0;
    r = (r * 10 + (s[i] - 48)) % m;
  }
  return Math::ModInt<int, MOD>(r == 0);
}
int main() {
  io >> m >> d;
  string a, b;
  io >> a >> b;
  io.WL((solve(b) - solve(a) + good(a)).x);
  return 0;
}

### Prompt

Develop a solution in CPP to the problem described below:

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 109 + 7 (so you should find the remainder after dividing by 109 + 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 109 + 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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
class IO {
  static const int bufSize = 1 << 18;
  char inBuf[bufSize], outBuf[bufSize];
  char *ip1 = inBuf, *ip2 = inBuf;
  int ok = 1, op1 = -1, op2 = bufSize - 1;
  template <typename T>
  __inline__ __attribute__((always_inline)) void __RI(T &x) {
    int ch = gc(), neg = 1;
    x = 0;
    for (; !(ch == EOF || isdigit(ch) || ch == '-'); ch = gc())
      ;
    if (ch == EOF) {
      ok = 0;
      return;
    }
    if (ch == '-') neg = -1, ch = gc();
    for (; isdigit(ch); ch = gc()) x = x * 10 + (ch - 48) * neg;
  }
  template <typename T>
  __inline__ __attribute__((always_inline)) void __RC(T &x) {
    unsigned char ch;
    while (isspace(ch = gc()))
      ;
    if (ch == EOF) {
      ok = 0;
      return;
    }
    x = ch;
  }
  __inline__ __attribute__((always_inline)) void __RS(string &x) {
    char ch;
    x.clear();
    for (ch = gc(); isspace(ch); ch = gc())
      ;
    if (ch == EOF) {
      ok = 0;
      return;
    }
    for (; !isspace(ch); ch = gc()) x.push_back(ch);
  }

 public:
  __inline__ __attribute__((always_inline)) int gc() {
    return ip1 == ip2 && (ip2 = (ip1 = inBuf) + fread(inBuf, 1, bufSize, stdin),
                          ip1 == ip2)
               ? EOF
               : *ip1++;
  }
  __inline__ __attribute__((always_inline)) IO &R(char &x) {
    __RC(x);
    return *this;
  }
  __inline__ __attribute__((always_inline)) IO &R(unsigned char &x) {
    __RC(x);
    return *this;
  }
  __inline__ __attribute__((always_inline)) IO &R(string &x) {
    __RS(x);
    return *this;
  }
  template <typename T1, typename T2>
  __inline__ __attribute__((always_inline)) IO &R(pair<T1, T2> &x) {
    R(x.first), R(x.second);
    return *this;
  }
  template <typename T>
  __inline__ __attribute__((always_inline)) IO &R(vector<T> &x) {
    for (auto &i : x) R(i);
    return *this;
  }
  template <typename T, typename... Args>
  __inline__ __attribute__((always_inline)) IO &RA(T *a, int n) {
    for (int i = 0; i < n; ++i) R(a[i]);
    return *this;
  }
  template <typename T, typename... Args>
  __inline__ __attribute__((always_inline)) IO &R(T &x, Args &...args) {
    R(x), R(args...);
    return *this;
  }
  template <typename T, typename... Args>
  __inline__ __attribute__((always_inline)) IO &RA(T *a, int n, Args... args) {
    for (int i = 0; i < n; ++i) RA(a[i], args...);
    return *this;
  }
  template <typename T>
  __inline__ __attribute__((always_inline)) IO &R(T &x) {
    static_assert(is_integral<T>::value, "Unsupported types");
    if (is_integral<T>::value) __RI(x);
    return *this;
  }

 private:
  char space = ' ';
  template <typename T>
  __inline__ __attribute__((always_inline)) void __WI(T x) {
    static char buf[64];
    static int len = -1;
    if (x >= 0) {
      do {
        buf[++len] = x % 10 + 48, x /= 10;
      } while (x);
    } else {
      pc('-');
      do {
        buf[++len] = -(x % 10) + 48, x /= 10;
      } while (x);
    }
    while (len >= 0) {
      pc(buf[len]), --len;
    }
  }

 public:
  __inline__ __attribute__((always_inline)) void pc(const char &x) {
    if (op1 == op2) flush();
    outBuf[++op1] = x;
  }
  __inline__ __attribute__((always_inline)) void flush() {
    fwrite(outBuf, 1, op1 + 1, stdout), op1 = -1;
  }
  __inline__ __attribute__((always_inline)) IO &W(const char &x) {
    pc(x);
    return *this;
  }
  __inline__ __attribute__((always_inline)) IO &W(const char *x) {
    while (*x != '\0') pc(*(x++));
    return *this;
  }
  __inline__ __attribute__((always_inline)) IO &W(const string &x) {
    W(x.c_str());
    return *this;
  }
  template <typename T>
  __inline__ __attribute__((always_inline)) IO &W(const vector<T> &x) {
    for (auto &i : x) WS(i);
    WL();
    return *this;
  }
  __inline__ __attribute__((always_inline)) IO &WL() {
    W('\n');
    return *this;
  }
  template <typename T1, typename T2>
  __inline__ __attribute__((always_inline)) IO &W(const pair<T1, T2> &x) {
    WS(x.first), W(x.second);
    return *this;
  }
  template <typename T>
  __inline__ __attribute__((always_inline)) IO &WL(const T &x) {
    W(x), W('\n');
    return *this;
  }
  __inline__ __attribute__((always_inline)) IO &WS() {
    W(space);
    return *this;
  }
  template <typename T>
  __inline__ __attribute__((always_inline)) IO &WS(const T &x) {
    W(x), W(space);
    return *this;
  }
  template <typename T>
  __inline__ __attribute__((always_inline)) IO &WA(T *a, int n) {
    for (int i = 0; i < n; i++) WS(a[i]);
    WL();
    return *this;
  }
  template <typename T, typename... Args>
  __inline__ __attribute__((always_inline)) IO &W(const T &x,
                                                  const Args &...args) {
    W(x), W(space), W(args...);
    return *this;
  }
  template <typename... Args>
  __inline__ __attribute__((always_inline)) IO &WS(const Args &...args) {
    W(args...), W(space);
    return *this;
  }
  template <typename... Args>
  __inline__ __attribute__((always_inline)) IO &WL(const Args &...args) {
    W(args...), W('\n');
    return *this;
  }
  template <typename T, typename... Args>
  __inline__ __attribute__((always_inline)) IO &WA(T *a, int n, Args... args) {
    for (int i = 0; i < n; i++) WA(a[i], args...);
    return *this;
  }
  template <typename T>
  __inline__ __attribute__((always_inline)) IO &W(const T &x) {
    static_assert(is_integral<T>::value, "Unsupported types");
    if (is_integral<T>::value) __WI(x);
    return *this;
  }
  template <typename T>
  __inline__ __attribute__((always_inline)) IO &operator>>(T &x) {
    R(x);
    return *this;
  }
  template <typename T>
  __inline__ __attribute__((always_inline)) IO &operator<<(const T &x) {
    W(x);
    return *this;
  }
  bool good() { return ok; }
  IO() {}
  ~IO() { flush(); }
} io;
const int32_t INF = 0x3f3f3f3f;
const int64_t INFL = 0x3f3f3f3f3f3f3f3fLL;
const int MOD = 1e9 + 7;
namespace Math {
template <typename T, typename T2>
inline T qpow(T a, T2 b) {
  T ans = 1;
  for (; b; b >>= 1) {
    if (b & 1) ans = (a * ans) % MOD;
    a = (a * a) % MOD;
  }
  return ans;
}
template <typename T>
inline T exgcd(T l, T r, T &x, T &y) {
  if (!r) {
    x = 1, y = 0;
    return l;
  } else {
    int d = exgcd(r, l % r, y, x);
    y -= l / r * x;
    return d;
  }
}
template <typename T>
inline T inv(T a) {
  return qpow(a, MOD - 2);
}
template <typename T>
inline T exinv(T a) {
  T x, y;
  exgcd(a, MOD, x, y);
  x %= MOD;
  return x + ((x >> (sizeof(T) * 8 - 1)) & MOD);
}
template <typename T, T MOD>
struct ModInt {
  T x;
  ModInt(T x = 0) : x(x) {
    while (x < 0) x += MOD;
  }
  ModInt<T, MOD> operator+=(const ModInt<T, MOD> &y) {
    x += y.x - MOD;
    x += (x >> (sizeof(T) * 8 - 1)) & MOD;
    return (*this);
  }
  ModInt<T, MOD> operator-=(const ModInt<T, MOD> &y) {
    x = x - y.x;
    x += (x >> (sizeof(T) * 8 - 1)) & MOD;
    return (*this);
  }
  ModInt<T, MOD> operator*=(const ModInt<T, MOD> &y) {
    x = x * y.x % MOD;
    return (*this);
  }
  ModInt<T, MOD> operator/=(const ModInt<T, MOD> &y) {
    x = x * inv(y.x) % MOD;
    return (*this);
  }
};
template <typename T, T MOD>
ModInt<T, MOD> operator+(ModInt<T, MOD> a, const ModInt<T, MOD> &b) {
  a += b;
  return a;
}
template <typename T, T MOD>
ModInt<T, MOD> operator-(ModInt<T, MOD> a, const ModInt<T, MOD> &b) {
  a -= b;
  return a;
}
template <typename T, T MOD>
ModInt<T, MOD> operator*(ModInt<T, MOD> a, const ModInt<T, MOD> &b) {
  a *= b;
  return a;
}
template <typename T, T MOD>
ModInt<T, MOD> operator/(ModInt<T, MOD> a, const ModInt<T, MOD> &b) {
  a /= b;
  return a;
}
template <typename T, T MOD>
ModInt<T, MOD> operator+(ModInt<T, MOD> a, const T &b) {
  a += ModInt<T, MOD>(b);
  return a;
}
template <typename T, T MOD>
ModInt<T, MOD> operator-(ModInt<T, MOD> a, const T &b) {
  a -= ModInt<T, MOD>(b);
  return a;
}
template <typename T, T MOD>
ModInt<T, MOD> operator*(ModInt<T, MOD> a, const T &b) {
  a *= ModInt<T, MOD>(b);
  return a;
}
template <typename T, T MOD>
ModInt<T, MOD> operator/(ModInt<T, MOD> a, const T &b) {
  a /= ModInt<T, MOD>(b);
  return a;
}
}  // namespace Math
const int MAXN = 3000;
Math::ModInt<int, MOD> dp[MAXN][MAXN][2];
int m, d;
Math::ModInt<int, MOD> solve(string s) {
  memset(dp, 0, sizeof(dp));
  dp[0][0][1] = 1;
  int n = s.size();
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      for (int k = 0; k < 2; k++)
        if (i & 1) {
          if (k == 1 && s[i] < '0' + d) continue;
          auto cur = dp[i][j][k];
          auto &nxt = dp[i + 1][(j * 10 + d) % m][k & (s[i] == '0' + d)];
          nxt += cur;
        } else
          for (int t = 0; t < 10; t++) {
            if (t == d) continue;
            if (k == 1 && s[i] < '0' + t) continue;
            auto cur = dp[i][j][k];
            auto &nxt = dp[i + 1][(j * 10 + t) % m][k & (s[i] == '0' + t)];
            nxt += cur;
          }
    }
  }
  Math::ModInt<int, MOD> ans = 0;
  for (int k = 0; k < 2; k++) ans += dp[n][0][k];
  return ans;
}
Math::ModInt<int, MOD> good(string s) {
  int r = 0;
  for (int i = 0; i < s.size(); i++) {
    if ((i & 1) ^ (s[i] == d + '0')) return 0;
    r = (r * 10 + (s[i] - 48)) % m;
  }
  return Math::ModInt<int, MOD>(r == 0);
}
int main() {
  io >> m >> d;
  string a, b;
  io >> a >> b;
  io.WL((solve(b) - solve(a) + good(a)).x);
  return 0;
}

```