Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chef likes assigning scores to pairs of numbers in an unusual way:
Consider a pair $(X, Y)$ of integers in decimal representation. If they don't have the same number of digits, add leading zeros to the smaller of these integers until they have the same number of digits. Let's denote the number of digits in each of the resulting decimal representations by $D$.
Reorder the digits of $Y$ in an arbitrary way.
For each $i$ ($1 ≤ i ≤ D$), calculate the absolute difference between the $i$-th digit of $X$ and the $i$-th digit of $Y$, and sum up these differences.
The score of the pair $(X, Y)$ is the minimum possible value of this sum.

Consider the pair $(3178, 10920)$ as an example. The scoring procedure would be:
Add a leading zero to $X$, so the decimal representations are "03178" and "10920".
Reorder "10920" e.g. to "01029".
The score is $|0-0| + |3-1| + |1-0| + |7-2| + |8-9| = 9$, since it is impossible to achieve a smaller sum.

Now, Chef has a range $[L, R]$, and he wants to calculate the sum of scores of all pairs of integers in this range ― formally, $\sum_{i=L}^{R} \sum_{j=L}^{R} \mathrm{score}(i, j)$. Since he is very busy with all his problem cooking, he asks you to write a program that would compute this sum. Since it could be very large, compute it modulo $1,000,000,007$.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first and only line of each test case contains two space-separated integers $L$ and $R$.

------  Output ------
For each test case, print a single line containing one integer ― the sum of scores modulo $1,000,000,007$.

------  Constraints ------
$1 ≤ T ≤ 50$
$1 ≤ L ≤ R ≤ 10^{18}$

------  Subtasks ------
Subtask #1 (10 points): $R ≤ 10^{3}$

Subtask #2 (40 points): $R ≤ 10^{9}$

Subtask #3 (20 points): $R ≤ 10^{12}$

Subtask #4 (30 points): original constraints

----- Sample Input 1 ------ 
2

1 10

3 17
----- Sample Output 1 ------ 
312

724

Difficulty: VERY_HARD
Tags: Dynamic programming

Complete search

Mathematics

Probability
Skill types: Dynamic programming

Complete search

Starter code:

Solutions:
import numpy as np
from sys import stdin
mod = 10 ** 9 + 7

def count(cur_pos, cur_cnt, cur_k, any_num_flag, num_lst, d, k):
	global dp
	if cur_pos == len(num_lst):
		if cur_k > 0 and cur_k - cur_cnt <= 0:
			return 1
		return 0
	if dp[cur_pos][cur_cnt][cur_k][any_num_flag] != -1:
		return dp[cur_pos][cur_cnt][cur_k][any_num_flag]
	ans = 0
	if any_num_flag:
		limit = 9
	else:
		limit = num_lst[cur_pos]
	for dig in range(limit + 1):
		tmp_cur_cnt = cur_cnt
		tmp_cur_k = cur_k
		if dig == d:
			tmp_cur_cnt += 1
		if dig < d:
			tmp_cur_k -= 1
		tmp_any_num_flag = any_num_flag
		if dig < num_lst[cur_pos]:
			tmp_any_num_flag = 1
		ans = (ans + count(cur_pos + 1, tmp_cur_cnt, max(0, tmp_cur_k), tmp_any_num_flag, num_lst, d, k)) % mod
	dp[cur_pos][cur_cnt][cur_k][any_num_flag] = ans
	return dp[cur_pos][cur_cnt][cur_k][any_num_flag]
M = 20
dp = None

def get_count_dct(num, max_len):
	global dp
	M = max_len + 1
	num_lst = []
	while num:
		num_lst.append(num % 10)
		num //= 10
	num_lst = num_lst + [0] * (max_len - len(num_lst))
	num_lst = num_lst[::-1]
	digit_loc_cnt = {}
	for i in range(10):
		dp = np.full((M, M, M, 2), -1).tolist()
		for j in range(max_len):
			digit_loc_cnt[i, j] = count(0, 0, j + 1, 0, num_lst, i, j + 1)
	return digit_loc_cnt
prev_cnt = {}
for _ in range(int(stdin.readline())):
	(l, r) = map(int, stdin.readline().split())
	max_len = len(str(r))
	if (l, max_len) in prev_cnt:
		l_count = prev_cnt[l, max_len]
	else:
		l_count = get_count_dct(l - 1, max_len)
		prev_cnt[l, max_len] = l_count
	if (r, max_len) in prev_cnt:
		r_count = prev_cnt[r, max_len]
	else:
		r_count = get_count_dct(r, max_len)
		prev_cnt[r, max_len] = r_count
	fin_count = {}
	for x in l_count:
		fin_count[x] = r_count[x] - l_count[x]
	ans = 0
	for i in range(10):
		for j in range(10):
			for k in range(max_len):
				ans = (ans + fin_count[i, k] * fin_count[j, k] * abs(i - j)) % mod
	print(ans % mod)