T3 Hash

using ll = long long;
constexpr ll hm = (1ll << 52) - 51;

ll f(ll x) {
    static const ll c1 = random(), c2 = random(), c3 = random(), c4 = random();
    return x * x * x * c1 + x * x + c2 + x * c3 + c4;
}

class Solution {
    vector<int> pmod;
    // using a2i = array<int, 2>;
    set<ll> valid;
    map<ll, ll> cnt;

    ll ans;
    void search(int beg, int end, int mod, int k, ll hash) {
        if (beg > end) {
            if (mod == 0) {
                if (valid.count(hash))
                    ans += 1;
                else {
                    ans += cnt[hash] + 1;
                    valid.insert(hash);
                }
            } else {
                if (valid.count(hash))
                    ans += 1;
            }
            cnt[hash] += 1;
            return;
        };
        for (int i = 0; i <= 9; ++i) {
            if (beg == 0 && i == 0) continue;
            if (beg != end)
                search(beg + 1, end - 1, (mod + i * (pmod[beg] + pmod[end])) % k, k, (hash + f(i) + f(i)) % hm);
            else
                search(beg + 1, end - 1, (mod + i * (pmod[beg])) % k, k, (hash + f(i)) % hm);
        }
    }
public:
    long long countGoodIntegers(int n, int k) {
        ans = 0;
        pmod = vector<int>(n + 1);
        pmod[0] = 1;
        for (int i = 1; i < n; ++i)
            pmod[i] = pmod[i - 1] * 10 % k;

        search(0, n - 1, 0, k, 0);

        return ans;
    }
};