628D Codeforces - DP Digit

//Make CSP great again
#include <bits/stdc++.h>
#define TASK "TESTCODE"
using namespace std;
const int N = 2e3, mod = 1e9 + 7;
string a, b;
int m, d;
int f[N + 1][2][N + 1];
void read()
{
    cin >> m >> d >> a >> b;
}
int dp(string &s, int i, bool low, int remain)
{
    if (i == s.length())
    {
        return remain == 0;
    }
    int &res = f[i][low][remain];
    if (res != -1)
    {
        return res;
    }
    res = 0;
    int k = s[i] - '0';
    if (low)
    {
        k = 9;
    }
    for (int j = 0; j <= k; ++ j)
    {
        if (i % 2 == 1 && j == d)
        {
            res += dp(s, i + 1, low | j < (s[i] - '0'), (remain * 10 + j) % m);
            res %= mod;
        }
        else if (i % 2 == 0 && j != d)
        {
            res += dp(s, i + 1, low | j < (s[i] - '0'), (remain * 10 + j) % m);
            res %= mod;
        }
    }
    return res;
}
int Get(string &s)
{
    memset(f, -1, sizeof(f));
    return dp(s, 0, 0, 0);
}
bool check()
{
    int sum = 0;
    for (int i = 0; i < a.length(); ++ i)
    {
        sum = (sum * 10 + a[i] - '0') % m;
        if (i % 2 == 1 && a[i] - '0' != d)
        {
            return false;
        }
        if (i % 2 == 0 && a[i] - '0' == d)
        {
            return false;
        }
    }
    return sum == 0;
}
void solve()
{
    cout << (Get(b) - Get(a) + check() + mod) % mod;;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen(TASK".INP", "r", stdin);
    //freopen(TASK".OUT", "w", stdout);
    int t = 1;
    bool typetest = false;
    if (typetest)
    {
        cin >> t;
    }
    for (int __ = 1; __ <= t; ++ __)
    {
        cerr << "Case " << __ << ": ";
        read();
        solve();
    }
}