1513C - Add One - CodeForces Solution

#include <bits/stdc++.h>
//#define ll long long
//#define int long long
#define vpii vector<pair<int, int>>
using namespace std;

#ifdef DMITRIY
#define _dbg(x) do { cout << #x << "=" << x << "; "; } while (0)
#define _name(name, _1, _2, _3, _4, N, ...) name ## N
#define _dbg1(x) _dbg(x)
#define _dbg2(x, ...) _dbg(x); _dbg1(__VA_ARGS__)
#define _dbg3(x, ...) _dbg(x); _dbg2(__VA_ARGS__)
#define _dbg4(x, ...) _dbg(x); _dbg3(__VA_ARGS__)
#define dbg(...) do { cout << __LINE__ << ": "; _name(_dbg, __VA_ARGS__, 4, 3, 2, 1, 0)(__VA_ARGS__); cout << endl;} while (0)
#else
#define dbg(...)
#endif

#define vi vector<int>
#define vvi vector<vector<int>>
#define vvvi vector<vector<vector<int>>>

//ввод вектора
template<typename T>
istream& operator>>(istream& o, vector<T> & a)
{
    for (size_t i = 0; i < a.size(); ++i){
        o >> a[i];
    }
    return o;
}

//вывод вектора
template<typename T>
ostream& operator<<(ostream& o, const vector<T> & a)
{
    for (size_t i = 0; i < a.size(); ++i){
        o << a[i] << " ";
    }
    o << '\n';
    return o;
}

void fast(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}

const int MOD = 1e9 + 7;
const int sz = 2e5 + 11;

vvvi get_dp(int m){
    vvvi dp(10, vvi (m + 11, vi(10, 0)));

    for(int l = 0; l <= 9; ++l){
        dp[l][0][l] = 1;
        for(int i = 1; i <= m + 10; ++i){
            for(int j = 0; j <= 9; ++j){
                if(j == 1){
                    dp[l][i][j] = dp[l][i-1][j-1] + dp[l][i-1][9];
                    dp[l][i][j] %= MOD;
                }
                else if(j == 0){
                    dp[l][i][j] = dp[l][i-1][9];
                }
                else{
                    dp[l][i][j] = dp[l][i-1][j-1];
                }
            }
        }
    }

    return dp;
}

vvvi dp = get_dp(sz);

void solve(){
    int n, m; cin >> n >> m;
    vi a(10);

    while(n != 0){
        a[n % 10]++;
        n /= 10;
    }

    int ans = 0;

    for(int i = 0; i <= 9; ++i){
        int sum = 0;
        for(int j = 0; j <= 9; ++j){
            sum += dp[i][m][j];
            sum %= MOD;
        }
        int z = sum;
        for(int ii = 0; ii < a[i]-1; ++ii){
            sum += z;
            sum %= MOD;
        }
        if(a[i] == 0){
            sum = 0;
        }
        //sum *= a[i];
        sum %= MOD;
        ans += sum;
        ans %= MOD;
    }

    cout << ans << "\n";




    return;
}

signed main(){
    #ifdef DMITRIY
    //freopen ("file.txt.txt","r",stdin);
    #endif
    fast();
    int tt = 1; cin >> tt;
    while(tt--){
        solve();
    }


    return 0;
}