95pts Wa #18 MnZn求助QAQ

#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <algorithm>

typedef long long valueType;
const valueType mod = 1e9 + 7;

int number[20];
valueType dp[20], power[20];
valueType record[20];

valueType Dfs(int pos, bool limit) {
    if (pos == 0)
        return 0;

    if (limit == false && dp[pos])
        return dp[pos];

    valueType result = 0;
    int biggest = (limit == true) ? number[pos] : 9;
    
    for (int i = 0; i <= biggest; ++ i) {
        if (limit && i == biggest) 
            result = (result + i * (record[pos] + 1) % mod) % mod;
        else 
            result = (result + i * power[pos - 1] % mod) % mod;

        result = (result + Dfs(pos - 1, (limit && (i == biggest)))) % mod;
    }

    if (!limit)
        dp[pos] = result;

    return result;
}

valueType Work(valueType ask) {
    if (ask <= 0) 
        return 0;

    memset(number, 0, sizeof(number));
    memset(record, 0, sizeof(record));

    int len = 1;

    while (ask) {
        if (ask % 10) 
            number[len] = ask % 10;
        
        record[len + 1] = (record[len] % mod + number[len] * power[len - 1] % mod) % mod;
        
        len ++;
        ask /= 10;
    }

    // std::reverse(number + 1, number + 1 + len - 1);

    // for (int i = len - 1; i >= 1; -- i) {
    //     std::cout << record[i] << " ";
    // }
    // std::cout << std::endl;

    return Dfs(len - 1, true);
}

int T;

void Pretreatment() {
    power[0] = 1;

    for (int i = 1; i <= 18; ++ i)
        power[i] = power[i - 1] * 10 % mod;
}

int main() {
    Pretreatment();

    scanf("%d", &T);

    while (T --) {
        valueType L, R;

        scanf("%lld%lld", &L, &R);

        printf("%lld\n", (Work(R) - Work(L - 1) + mod) % mod);

        // std::cin >> L;

        // std::cout << Work(L) << std::endl;
    }

    return 0;
}
/*
1 
91 109
*/