H. Lucky numbers

#include <bits/stdc++.h>

#define ll long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define boost ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define watch(x) cout << (#x) << " : " << x << '\n'

using namespace std;

const int N = 111;
const int DIG = 10;
const int SUM = N * DIG;

const int MOD = 1e9 + 7;

ll cnt[N][SUM][DIG];
ll ruk[N][SUM][DIG + 1];

ll binpow(ll a, ll n) {
    ll res = 1ll;
    while (n) {
        if (n & 1)
            res = (res * a) % MOD;
        a = (a * a) % MOD;
        n >>= 1;
    }
    return res;
}

ll inverse_element(ll a) {
    return binpow(a, MOD - 2);
}

ll divide(ll a, ll b) {
    return (a * inverse_element(b)) % MOD;
}

ll fact[N];

ll C(ll k, ll n) {
    return divide(fact[n], (fact[k] * fact[n - k]) % MOD);
}

void solve() {
    int n;
    cin >> n;

    fact[0] = fact[1] = 1;
    for (int i = 2; i < N; i++)
        fact[i] = (fact[i - 1] * i) % MOD;

    for (int d = 0; d < DIG; d++)
        ruk[0][0][d] = 1;

    for (int i = 1; i <= n; i++) {
        for (int blocked = 0; blocked <= DIG; blocked++) {
            for (int d = 0; d < DIG; d++) {
                if (d == blocked)
                    continue;
                for (int target = 0; target < SUM; target++) {
                    if (target + d >= SUM)
                        break;
                    ruk[i][target + d][blocked] += ruk[i - 1][target][blocked];
                    if (ruk[i][target + d][blocked] >= MOD)
                        ruk[i][target + d][blocked] -= MOD;
                }
            }
        }
    }

    for (int d = 0; d < DIG; d++)
        for (int use = 0; use <= n; use++) {
            for (int sum = 0; sum < SUM; sum++) {
                if (sum + use * d >= SUM)
                    break;
                int ost_nums = n - use;
                cnt[use][sum + use * d][d] += (ruk[ost_nums][sum][d] * C(use, n)) % MOD;
                cnt[use][sum + use * d][d] %= MOD;
            }
        }

    for (int d = 0; d < DIG; d++) {
        ll ans = 0ll;
        for (int sum = 0; sum < SUM; sum++) {
            for (int use_left = 0; use_left <= n; use_left++) {
                for (int use_right = use_left; use_right <= n; use_right++) {
                    if (!use_left && !use_right)
                        continue;
                    int tot = use_left + use_right;

                    ll ways = (cnt[use_left][sum][d] * cnt[use_right][sum][d]) % MOD;
                    if (use_left != use_right) ways = (ways * 2) % MOD;

                    ans += (ways * tot) % MOD;
                    ans %= MOD;
                }
            }
        }
        cout << ans << ' ';
    }
}

signed main() {
    boost;
    solve();
    return 0;
}