1class Solution {
2    // Modulus value commonly used to prevent integer overflow in results.
3    private static final int MOD = 1_000_000_007;
4
5    public int sumOfNumbers(int l, int r, int k) {
6        // Count of integers in the inclusive range [l, r].
7        long count = r - l + 1L;
8
9        // Arithmetic series sum of the range [l, r]:
10        // (l + r) * count / 2, taken modulo MOD.
11        // Division by 2 is done before taking the modulo because
12        // (l + r) * count is guaranteed to be even.
13        long rangeSum = (long) (l + r) * count / 2 % MOD;
14
15        // count^(k - 1) mod MOD.
16        // This accounts for the number of ways the remaining (k - 1)
17        // positions can be filled by values in the range.
18        long countPow = qpow(count % MOD, k - 1, MOD);
19
20        // (10^k - 1) mod MOD.
21        // This is the numerator of the repunit-like factor representing
22        // the place values 1, 10, 100, ... summed across k positions.
23        // Adding MOD before the final modulo guards against a negative result.
24        long placeValueNumerator = (qpow(10, k, MOD) - 1 + MOD) % MOD;
25
26        // Modular inverse of 9 using Fermat's little theorem:
27        // 9^(MOD - 2) mod MOD, valid because MOD is prime.
28        // Multiplying by inv9 is equivalent to dividing by 9, which
29        // converts (10^k - 1) into the geometric series sum (10^k - 1) / 9.
30        long inv9 = qpow(9, MOD - 2, MOD);
31
32        // Combine all factors step by step, applying the modulo each time.
33        long ans = rangeSum;
34        ans = ans * countPow % MOD;
35        ans = ans * placeValueNumerator % MOD;
36        ans = ans * inv9 % MOD;
37
38        return (int) ans;
39    }
40
41    /**
42     * Computes (base^exp) mod modulus using fast exponentiation (binary exponentiation).
43     *
44     * @param base    the base value
45     * @param exp     the exponent (assumed non-negative)
46     * @param modulus the modulus
47     * @return (base^exp) mod modulus
48     */
49    private int qpow(long base, int exp, int modulus) {
50        long result = 1;
51        base %= modulus;
52
53        // Process each bit of the exponent from least significant to most significant.
54        for (; exp > 0; exp >>= 1) {
55            // If the current lowest bit is set, multiply the result by the current base.
56            if ((exp & 1) == 1) {
57                result = result * base % modulus;
58            }
59            // Square the base for the next bit position.
60            base = base * base % modulus;
61        }
62
63        return (int) result;
64    }
65}
66

1class Solution {
2public:
3    int sumOfNumbers(int l, int r, int k) {
4        const int kMod = 1'000'000'007;
5
6        // Count of integers in the inclusive range [l, r].
7        long long count = 1LL * r - l + 1;
8
9        // Sum of the arithmetic sequence from l to r:
10        // ((l + r) * count / 2) % kMod.
11        long long rangeSum = 1LL * (l + r) * count / 2 % kMod;
12
13        // count^(k - 1) % kMod, contributing the scaling factor for the
14        // k-block construction.
15        long long countPow = qpow(count % kMod, k - 1, kMod);
16
17        // (10^k - 1) % kMod, the numerator of the repunit value.
18        long long repunitNumerator = (qpow(10, k, kMod) - 1 + kMod) % kMod;
19
20        // Modular inverse of 9 via Fermat's little theorem:
21        // 9^(kMod - 2) % kMod, used to divide by 9 under the modulus.
22        long long inverseOfNine = qpow(9, kMod - 2, kMod);
23
24        // Combine all factors modulo kMod:
25        // rangeSum * count^(k-1) * (10^k - 1) / 9.
26        long long answer = rangeSum;
27        answer = answer * countPow % kMod;
28        answer = answer * repunitNumerator % kMod;
29        answer = answer * inverseOfNine % kMod;
30
31        return static_cast<int>(answer);
32    }
33
34private:
35    // Fast modular exponentiation: computes (base^exponent) % mod
36    // in O(log(exponent)) time using binary exponentiation.
37    long long qpow(long long base, long long exponent, int mod) {
38        long long result = 1;
39        base %= mod;
40        while (exponent > 0) {
41            // If the current lowest bit is set, accumulate the current base.
42            if (exponent & 1) {
43                result = result * base % mod;
44            }
45            // Square the base for the next bit position.
46            base = base * base % mod;
47            exponent >>= 1;
48        }
49        return result;
50    }
51};
52

1const MOD = 1_000_000_007n;
2
3/**
4 * Fast modular exponentiation: computes (base ^ exp) % mod.
5 */
6function qpow(base: bigint, exp: bigint, mod: bigint): bigint {
7    base %= mod;
8    let result = 1n;
9    while (exp > 0n) {
10        // If the current lowest bit is set, multiply result by the current base.
11        if ((exp & 1n) === 1n) {
12            result = (result * base) % mod;
13        }
14        // Square the base for the next bit.
15        base = (base * base) % mod;
16        exp >>= 1n;
17    }
18    return result;
19}
20
21/**
22 * Computes the weighted sum of numbers from l to r, where each value is spread
23 * across k digit positions, returning the answer modulo 1e9+7.
24 */
25function sumOfNumbers(l: number, r: number, k: number): number {
26    // Count of integers in the inclusive range [l, r].
27    const count = BigInt(r - l + 1);
28
29    // Arithmetic series sum of [l, r]: ((l + r) * count) / 2, taken modulo MOD.
30    // The product (l + r) * count is always even, so integer division by 2 is exact.
31    const sum = ((BigInt(l + r) * count) / 2n) % MOD;
32
33    // count ^ (k - 1): the combinatorial factor for distributing values across positions.
34    const part1 = qpow(count % MOD, BigInt(k - 1), MOD);
35
36    // 10^k - 1: numerator of the repunit (111...1 with k ones); add MOD to stay non-negative.
37    const part2 = (qpow(10n, BigInt(k), MOD) - 1n + MOD) % MOD;
38
39    // Modular inverse of 9 via Fermat's little theorem, since (10^k - 1) / 9 = 111...1 (k ones).
40    const inv9 = qpow(9n, MOD - 2n, MOD);
41
42    // Combine all factors modulo MOD.
43    let ans = sum;
44    ans = (ans * part1) % MOD;
45    ans = (ans * part2) % MOD;
46    ans = (ans * inv9) % MOD;
47
48    return Number(ans);
49}
50