牛牛的函数2

#define lint __int128_t
const lint MOD = 10000000033;

class Solution {
public:
    lint quickMul(lint a, lint b) {
        return (a * b - (lint)((long double)a / MOD * b) * MOD + MOD) % MOD;
    }
    
    lint quickPow(lint a, lint b) {
        lint res = 1;
        while (b) {
            if (b & 1) res = quickMul(res, a);
            b >>= 1;
            a = quickMul(a, a);
        }
        return res;
    }
    
    lint stolint(string s) {
        lint res = 0, i = 1;
        for (int j = s.length() - 1; j >= 0; i *= 10, j--) res += i * (s[j] - '0');
        return res;
    }
    
    long long solve(string sa, string sb, int n) {
        if (n == 0) return 0;
        lint a = stolint(sa), b = stolint(sb);
        if (n == 1) return quickMul(quickMul(a + 1 + b, b - a), quickPow(2, MOD - 2));
        lint na = quickPow(n, a), nb = quickPow(n, b);
        lint c = (quickMul(quickMul(na, n), a) - quickMul(na, a + 1) + MOD) % MOD;
        lint d = (quickMul(quickMul(nb, n), b) - quickMul(nb, b + 1) + MOD) % MOD;
        return quickMul((d - c + MOD) % MOD, quickPow(n - 1, MOD - 3));
    }
};