Your task is to calculate the sum (indicated by S) of all the k-balanced integers between [L, R]. An integer is called k-balanced when either of #1 or #2 below holds true.

The length of the integer <= k     
Sum of the first k digits (with no leading zeros) is equal to the sum of the last k digits.    

Input format 

L R k

Output format 

S % 1000000007

Constraints 

0 < L <= R < 10^18 

0 < k <= 18

Sample Input 

9 23 1

Sample Output 

42

Explanation 

9, 11 and 22 are the only 3 integers between 9 and 23 ( both included ) that are k-balanced. Hence, the answer is 9+11+22=42

Difficulty: MEDIUM_HARD
Tags: Combinatorics

Starter code:

Solutions:
from itertools import zip_longest
MOD = 1000000007

def n_digit_counts_and_sums(n):
	counts = [[1]]
	sums = [[0]]
	for _ in range(1, n + 1):
		prev_counts = counts[-1]
		prev_sums = sums[-1]
		new_counts = [0 for _ in range(len(prev_counts) + 9)]
		new_sums = [0 for _ in range(len(prev_sums) + 9)]
		for i in range(10):
			for j in range(len(prev_counts)):
				new_counts[i + j] += prev_counts[j]
				new_sums[i + j] = (new_sums[i + j] + prev_sums[j] * 10 + i * prev_counts[j]) % MOD
		counts.append(new_counts)
		sums.append(new_sums)
	return (counts, sums)

def subtract(a, b):
	return [i - j for (i, j) in zip_longest(a, b, fillvalue=0)]

def all_to_n_digit(array):
	return [[0]] + [subtract(array[n], array[n - 1]) for n in range(1, len(array))]

def bounded_number_counts_and_sums(digits, all_counts, all_sums):
	if len(digits) == 0:
		return ([0], [0])
	first_digit = digits[0]
	if len(digits) == 1:
		return ([1 for _ in range(first_digit + 1)] + [0 for _ in range(9 - first_digit)], [i for i in range(first_digit + 1)] + [0 for _ in range(9 - first_digit)])
	(first_digit_counts, first_digit_sums) = bounded_number_counts_and_sums(digits[1:], all_counts, all_sums)
	(prev_counts, prev_sums) = (all_counts[len(digits) - 1], all_sums[len(digits) - 1])
	result_counts = [0 for _ in range(len(prev_counts) + 9)]
	result_sums = [0 for _ in range(len(prev_sums) + 9)]
	for i in range(first_digit):
		for j in range(len(prev_counts)):
			result_counts[i + j] += prev_counts[j]
			result_sums[i + j] = (result_sums[i + j] + prev_sums[j] + i * prev_counts[j] * 10 ** (len(digits) - 1)) % MOD
	for j in range(len(first_digit_counts)):
		result_counts[first_digit + j] += first_digit_counts[j]
		result_sums[first_digit + j] = (result_sums[first_digit + j] + first_digit_sums[j] + first_digit * first_digit_counts[j] * 10 ** (len(digits) - 1)) % MOD
	return (result_counts, result_sums)

def solve(N, k):
	digits = [int(c) for c in f'{N}']
	len_N = len(digits)
	if len(digits) <= k:
		return N * (N + 1) // 2 % MOD
	(counts, sums) = n_digit_counts_and_sums(min(k, len_N - k))
	(counts1, sums1) = (all_to_n_digit(counts), all_to_n_digit(sums))
	result_sum = 10 ** k * (10 ** k - 1) // 2 % MOD
	for N1 in range(k + 1, len_N):
		kk = min(k, N1 - k)
		len_cnt = N1 - 2 * kk
		center_sum = 10 ** len_cnt * (10 ** len_cnt - 1) * 10 ** kk // 2 % MOD
		center_count = 10 ** len_cnt
		for (i_count, i_sum, j_count, j_sum) in zip(counts1[kk], sums1[kk], counts[kk], sums[kk]):
			result_sum = (result_sum + i_sum * 10 ** (len_cnt + kk) * center_count * j_count + i_count * center_sum * j_count + i_count * center_count * j_sum) % MOD
	kk = min(k, len_N - k)
	len_cnt = len_N - 2 * kk
	(end_counts_bounded, end_sums_bounded) = bounded_number_counts_and_sums(digits[-kk:], counts, sums)
	kk_digits_sum = sum(digits[:kk])
	low_bound = int(str(N)[:kk + len_cnt] + '0' * kk)
	result_sum = (result_sum + low_bound * end_counts_bounded[kk_digits_sum] + end_sums_bounded[kk_digits_sum]) % MOD
	cnt_number = int(str(N)[kk:kk + len_cnt] or 0)
	cnt_count = cnt_number
	cnt_sum = cnt_number * (cnt_number - 1) * 10 ** kk // 2
	start_sum = int(str(N)[:kk] + '0' * (kk + len_cnt))
	result_sum = (result_sum + start_sum * cnt_count * counts[kk][kk_digits_sum] + cnt_sum * counts[kk][kk_digits_sum] + cnt_count * sums[kk][kk_digits_sum]) % MOD
	center_sum = 10 ** len_cnt * (10 ** len_cnt - 1) * 10 ** kk // 2 % MOD
	center_count = 10 ** len_cnt
	(start_counts0, start_sums0) = bounded_number_counts_and_sums(digits[:kk], counts, sums)
	start_counts = subtract(start_counts0, counts[kk - 1])
	start_sums = subtract(start_sums0, sums[kk - 1])
	start_counts[kk_digits_sum] -= 1
	start_sums[kk_digits_sum] -= int(str(N)[:kk])
	for (i_count, i_sum, j_count, j_sum) in zip(start_counts, start_sums, counts[kk], sums[kk]):
		result_sum = (result_sum + i_sum * 10 ** (len_cnt + kk) * center_count * j_count + i_count * center_sum * j_count + i_count * center_count * j_sum) % MOD
	return result_sum
(L, R, k) = list(map(int, input().split()))
result = (solve(R, k) - solve(L - 1, k)) % MOD
print(result)


from collections import defaultdict
mod = 1000000007
reps = [defaultdict(lambda : 0)]
sums = [defaultdict(lambda : 0)]
reps[0][0] = 1
sums[0][0] = 0
pow10list = [1]
for i in range(18):
	reptoapp = defaultdict(lambda : 0)
	sumtoapp = defaultdict(lambda : 0)
	for j in reps[-1].keys():
		for k in range(10):
			reptoapp[j + k] += reps[-1][j]
			sumtoapp[j + k] += 10 * sums[-1][j] + reps[-1][j] * k
	reps.append(reptoapp)
	sums.append(sumtoapp)
	pow10list.append(10 * pow10list[-1])

def subbal(n, k):
	diglist = []
	curr = n
	while curr > 0:
		diglist.append(curr % 10)
		curr //= 10
	diglist.reverse()
	toret = 0
	frontk = k if 2 * k <= len(diglist) else len(diglist) - k
	frontsum = 0
	frontval = 0
	for i in range(frontk):
		currdig = diglist[i]
		for j in range(1 if i == 0 else 0, currdig):
			initsubsum = frontsum + j
			frontsubval = 10 * frontval + j
			for endsum in reps[frontk].keys():
				currfrontsum = endsum - initsubsum
				nummid = pow10list[len(diglist) - 2 * frontk]
				toret += frontsubval * pow10list[len(diglist) - i - 1] * reps[frontk - i - 1][currfrontsum] * reps[frontk][endsum] * nummid
				toret += sums[frontk - i - 1][currfrontsum] * pow10list[len(diglist) - frontk] * reps[frontk][endsum] * nummid
				toret += reps[frontk - i - 1][currfrontsum] * reps[frontk][endsum] * (nummid * (nummid - 1)) // 2 * pow10list[frontk]
				toret += reps[frontk - i - 1][currfrontsum] * sums[frontk][endsum] * nummid
		frontsum += currdig
		frontval = 10 * frontval + currdig
	for i in range(frontk, len(diglist) - frontk):
		currdig = diglist[i]
		nummid = pow10list[len(diglist) - i - frontk - 1]
		for j in range(currdig):
			frontsubval = 10 * frontval + j
			toret += frontsubval * reps[frontk][frontsum] * pow10list[len(diglist) - i - 1] * nummid
			toret += nummid * (nummid - 1) // 2 * pow10list[frontk] * reps[frontk][frontsum]
			toret += nummid * sums[frontk][frontsum]
		frontval = 10 * frontval + currdig
	endsum = frontsum
	for i in range(len(diglist) - frontk, len(diglist)):
		currdig = diglist[i]
		for j in range(currdig):
			frontsubval = 10 * frontval + j
			currendsum = endsum - j
			toret += frontsubval * reps[len(diglist) - i - 1][currendsum] * pow10list[len(diglist) - i - 1]
			toret += sums[len(diglist) - i - 1][currendsum]
		frontval = 10 * frontval + currdig
		endsum -= currdig
	return toret

def subbalwrapper(n, k):
	diglen = len(str(n))
	if diglen <= k:
		return n * (n - 1) // 2
	toret = subbal(n, k) + (pow10list[k] - 1) * (pow10list[k] // 2)
	for i in range(k + 1, diglen):
		toret += pow10list[i] - 1 + subbal(pow10list[i] - 1, k)
	return toret
[l, r, k] = list(map(int, input().split()))
print((subbalwrapper(r + 1, k) - subbalwrapper(l, k)) % mod)


from itertools import zip_longest
MOD = 1000000007

def n_digit_counts_and_sums(n):
	counts = [[1]]
	sums = [[0]]
	for _ in range(1, n + 1):
		prev_counts = counts[-1]
		prev_sums = sums[-1]
		new_counts = [0 for _ in range(len(prev_counts) + 9)]
		new_sums = [0 for _ in range(len(prev_sums) + 9)]
		for i in range(10):
			for j in range(len(prev_counts)):
				new_counts[i + j] += prev_counts[j]
				new_sums[i + j] = (new_sums[i + j] + prev_sums[j] * 10 + i * prev_counts[j]) % MOD
		counts.append(new_counts)
		sums.append(new_sums)
	return (counts, sums)

def subtract(a, b):
	return [i - j for (i, j) in zip_longest(a, b, fillvalue=0)]

def all_to_n_digit(array):
	return [[0]] + [subtract(array[n], array[n - 1]) for n in range(1, len(array))]

def bounded_number_counts_and_sums(digits, all_counts, all_sums):
	if len(digits) == 0:
		return ([0], [0])
	first_digit = digits[0]
	if len(digits) == 1:
		return ([1 for _ in range(first_digit + 1)] + [0 for _ in range(9 - first_digit)], [i for i in range(first_digit + 1)] + [0 for _ in range(9 - first_digit)])
	(first_digit_counts, first_digit_sums) = bounded_number_counts_and_sums(digits[1:], all_counts, all_sums)
	(prev_counts, prev_sums) = (all_counts[len(digits) - 1], all_sums[len(digits) - 1])
	result_counts = [0 for _ in range(len(prev_counts) + 9)]
	result_sums = [0 for _ in range(len(prev_sums) + 9)]
	for i in range(first_digit):
		for j in range(len(prev_counts)):
			result_counts[i + j] += prev_counts[j]
			result_sums[i + j] = (result_sums[i + j] + prev_sums[j] + i * prev_counts[j] * 10 ** (len(digits) - 1)) % MOD
	for j in range(len(first_digit_counts)):
		result_counts[first_digit + j] += first_digit_counts[j]
		result_sums[first_digit + j] = (result_sums[first_digit + j] + first_digit_sums[j] + first_digit * first_digit_counts[j] * 10 ** (len(digits) - 1)) % MOD
	return (result_counts, result_sums)

def solve(N, k):
	digits = [int(c) for c in f'{N}']
	len_N = len(digits)
	if len(digits) <= k:
		return N * (N + 1) // 2 % MOD
	(counts, sums) = n_digit_counts_and_sums(min(k, len_N - k))
	(counts1, sums1) = (all_to_n_digit(counts), all_to_n_digit(sums))
	result_sum = 10 ** k * (10 ** k - 1) // 2 % MOD
	for N1 in range(k + 1, len_N):
		kk = min(k, N1 - k)
		len_cnt = N1 - 2 * kk
		center_sum = 10 ** len_cnt * (10 ** len_cnt - 1) * 10 ** kk // 2 % MOD
		center_count = 10 ** len_cnt
		for (i_count, i_sum, j_count, j_sum) in zip(counts1[kk], sums1[kk], counts[kk], sums[kk]):
			result_sum = (result_sum + i_sum * 10 ** (len_cnt + kk) * center_count * j_count + i_count * center_sum * j_count + i_count * center_count * j_sum) % MOD
	kk = min(k, len_N - k)
	len_cnt = len_N - 2 * kk
	(end_counts_bounded, end_sums_bounded) = bounded_number_counts_and_sums(digits[-kk:], counts, sums)
	kk_digits_sum = sum(digits[:kk])
	low_bound = int(str(N)[:kk + len_cnt] + '0' * kk)
	result_sum = (result_sum + low_bound * end_counts_bounded[kk_digits_sum] + end_sums_bounded[kk_digits_sum]) % MOD
	cnt_number = int(str(N)[kk:kk + len_cnt] or 0)
	cnt_count = cnt_number
	cnt_sum = cnt_number * (cnt_number - 1) * 10 ** kk // 2
	start_sum = int(str(N)[:kk] + '0' * (kk + len_cnt))
	result_sum = (result_sum + start_sum * cnt_count * counts[kk][kk_digits_sum] + cnt_sum * counts[kk][kk_digits_sum] + cnt_count * sums[kk][kk_digits_sum]) % MOD
	center_sum = 10 ** len_cnt * (10 ** len_cnt - 1) * 10 ** kk // 2 % MOD
	center_count = 10 ** len_cnt
	(start_counts0, start_sums0) = bounded_number_counts_and_sums(digits[:kk], counts, sums)
	start_counts = subtract(start_counts0, counts[kk - 1])
	start_sums = subtract(start_sums0, sums[kk - 1])
	start_counts[kk_digits_sum] -= 1
	start_sums[kk_digits_sum] -= int(str(N)[:kk])
	for (i_count, i_sum, j_count, j_sum) in zip(start_counts, start_sums, counts[kk], sums[kk]):
		result_sum = (result_sum + i_sum * 10 ** (len_cnt + kk) * center_count * j_count + i_count * center_sum * j_count + i_count * center_count * j_sum) % MOD
	return result_sum
(L, R, k) = list(map(int, input().split()))
result = (solve(R, k) - solve(L - 1, k)) % MOD
print(result)


from itertools import zip_longest
MOD = 1000000007

def n_digit_counts_and_sums(n):
	counts = [[1]]
	sums = [[0]]
	for _ in range(1, n + 1):
		prev_counts = counts[-1]
		prev_sums = sums[-1]
		new_counts = [0 for _ in range(len(prev_counts) + 9)]
		new_sums = [0 for _ in range(len(prev_sums) + 9)]
		for i in range(10):
			for j in range(len(prev_counts)):
				new_counts[i + j] += prev_counts[j]
				new_sums[i + j] = (new_sums[i + j] + prev_sums[j] * 10 + i * prev_counts[j]) % MOD
		counts.append(new_counts)
		sums.append(new_sums)
	return (counts, sums)

def subtract(a, b):
	return [i - j for (i, j) in zip_longest(a, b, fillvalue=0)]

def all_to_n_digit(array):
	return [[0]] + [subtract(array[n], array[n - 1]) for n in range(1, len(array))]

def bounded_number_counts_and_sums(digits, all_counts, all_sums):
	if len(digits) == 0:
		return ([0], [0])
	first_digit = digits[0]
	if len(digits) == 1:
		return ([1 for _ in range(first_digit + 1)] + [0 for _ in range(9 - first_digit)], [i for i in range(first_digit + 1)] + [0 for _ in range(9 - first_digit)])
	(first_digit_counts, first_digit_sums) = bounded_number_counts_and_sums(digits[1:], all_counts, all_sums)
	(prev_counts, prev_sums) = (all_counts[len(digits) - 1], all_sums[len(digits) - 1])
	result_counts = [0 for _ in range(len(prev_counts) + 9)]
	result_sums = [0 for _ in range(len(prev_sums) + 9)]
	for i in range(first_digit):
		for j in range(len(prev_counts)):
			result_counts[i + j] += prev_counts[j]
			result_sums[i + j] = (result_sums[i + j] + prev_sums[j] + i * prev_counts[j] * 10 ** (len(digits) - 1)) % MOD
	for j in range(len(first_digit_counts)):
		result_counts[first_digit + j] += first_digit_counts[j]
		result_sums[first_digit + j] = (result_sums[first_digit + j] + first_digit_sums[j] + first_digit * first_digit_counts[j] * 10 ** (len(digits) - 1)) % MOD
	return (result_counts, result_sums)

def solve(N, k):
	digits = [int(c) for c in f'{N}']
	len_N = len(digits)
	if len(digits) <= k:
		return N * (N + 1) // 2 % MOD
	(counts, sums) = n_digit_counts_and_sums(min(k, len_N - k))
	(counts1, sums1) = (all_to_n_digit(counts), all_to_n_digit(sums))
	result_sum = 10 ** k * (10 ** k - 1) // 2 % MOD
	for N1 in range(k + 1, len_N):
		kk = min(k, N1 - k)
		len_cnt = N1 - 2 * kk
		center_sum = 10 ** len_cnt * (10 ** len_cnt - 1) * 10 ** kk // 2 % MOD
		center_count = 10 ** len_cnt
		for (i_count, i_sum, j_count, j_sum) in zip(counts1[kk], sums1[kk], counts[kk], sums[kk]):
			result_sum = (result_sum + i_sum * 10 ** (len_cnt + kk) * center_count * j_count + i_count * center_sum * j_count + i_count * center_count * j_sum) % MOD
	kk = min(k, len_N - k)
	len_cnt = len_N - 2 * kk
	(end_counts_bounded, end_sums_bounded) = bounded_number_counts_and_sums(digits[-kk:], counts, sums)
	kk_digits_sum = sum(digits[:kk])
	low_bound = int(str(N)[:kk + len_cnt] + '0' * kk)
	result_sum = (result_sum + low_bound * end_counts_bounded[kk_digits_sum] + end_sums_bounded[kk_digits_sum]) % MOD
	cnt_number = int(str(N)[kk:kk + len_cnt] or 0)
	cnt_count = cnt_number
	cnt_sum = cnt_number * (cnt_number - 1) * 10 ** kk // 2
	start_sum = int(str(N)[:kk] + '0' * (kk + len_cnt))
	result_sum = (result_sum + start_sum * cnt_count * counts[kk][kk_digits_sum] + cnt_sum * counts[kk][kk_digits_sum] + cnt_count * sums[kk][kk_digits_sum]) % MOD
	center_sum = 10 ** len_cnt * (10 ** len_cnt - 1) * 10 ** kk // 2 % MOD
	center_count = 10 ** len_cnt
	(start_counts0, start_sums0) = bounded_number_counts_and_sums(digits[:kk], counts, sums)
	start_counts = subtract(start_counts0, counts[kk - 1])
	start_sums = subtract(start_sums0, sums[kk - 1])
	start_counts[kk_digits_sum] -= 1
	start_sums[kk_digits_sum] -= int(str(N)[:kk])
	for (i_count, i_sum, j_count, j_sum) in zip(start_counts, start_sums, counts[kk], sums[kk]):
		result_sum = (result_sum + i_sum * 10 ** (len_cnt + kk) * center_count * j_count + i_count * center_sum * j_count + i_count * center_count * j_sum) % MOD
	return result_sum
(L, R, k) = list(map(int, input().split()))
result = (solve(R, k) - solve(L - 1, k)) % MOD
print(result)