SP10476 IOPC1206 - Fair bases

给定整数 $N$ 和 $K$，其中 $2 \leq K \leq N$。我们用 $K$ 进制表示创建一个长度为 $N$ 的所有非负整数的列表，这些整数的每一位数字都在 $0$ 到 $K-1$ 之间，并且没有前导零。 例如，假设 $N=4$，$K=3$。则列表中的数字为 $00, 01, 02$ 和 $10$。我们来计算数字 $00$ 的得分。$00$ 的第一位在第一位出现了三次（$00, 01, 02$），第二位在第二位出现了两次（$00, 10$）。因此，$00$ 的得分为 $3+2=5$。 对于每个整数 $K$ 在此范围内，我们定义每个数字 $i$ 的“公平因子”即为其在列表中的得分。给定两个整数 $a$ 和 $b$（$2 \leq a \leq b \leq 10^9$），要求计算范围 $a$ 到 $b$ 内所有整数 $i$ 的公平因子之和。

第一行包含一个整数 $T$，表示测试用例的数量（$1 \leq T \leq 1000$）。接下来的 $T$ 行中，每行包含两个整数 $a$ 和 $b$，表示要求和的区间（$2 \leq a \leq b \leq 10^9$）。

对于每一个输入的区间 $(a, b)$，输出该区间内所有整数的公平因子之和。结果可能非常大，请对 $10^9 + 7$ 取模后输出。 **本翻译由 AI 自动生成**