← 返回题目列表

Codeforces · 1513/C

C. 添加一个

中文机器翻译题面 查看原题

给你一个整数$$$n$$$。您必须对其应用 $$$m$$$ 操作。

在一次操作中,您必须将数字 $$$d$$$ 的每一位数字替换为整数 $$$d + 1$$$ 的十进制表示形式。例如,$$$1912$$$ 在应用一次操作后变为 $$$21023$$$。

在应用 $$$m$$$ 操作后,您必须找到 $$$n$$$ 的长度。由于答案可能非常大,因此打印它对 $$$10^9+7$$$ 取模。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$) — 测试用例的数量。

每个测试用例的唯一行包含两个整数 $$$n$$$ ($$$1 \le n \le 10^9$$$) 和 $$$m$$$ ($$$1 \le m \le 2 \cdot 10^5$$$) – 初始数量和操作数量。

输出

对于每个测试用例,输出结果数字的长度模$$$10^9+7$$$。

示例

输入 #1

5
1912 1
5 6
999 1
88 2
12 100

输出 #1

5
2
6
4
2115

注意

对于第一个测试,在长度为 $$$5$$$ 的 $$$1$$$ 操作之后,$$$1912$$$ 变为 $$$21023$$$。

对于第二个测试,在长度为 $$$2$$$ 的 $$$6$$$ 操作之后,$$$5$$$ 变为 $$$21$$$。

对于第三个测试,在长度为 $$$6$$$ 的 $$$1$$$ 操作之后,$$$999$$$ 变为 $$$101010$$$。

对于第四个测试,在长度为 $$$4$$$ 的 $$$2$$$ 操作之后,$$$88$$$ 变为 $$$1010$$$。