← 返回题目列表

AtCoder · icpc2013spring_b

B. 整数中的整数

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

问题陈述

给定一个整数区间 \[A, B\] 和一个整数 C,你的工作是计算出现的次数 C 作为间隔中的字符串。

例如, 33 出现在 333 两次,并出现在 334 一次。因此出现的次数 33 in \[333, 334\] is 3.


输入

测试用例由一行三个整数给出, A, B, C (0 \leq A \leq B \leq 10^{10000}, 0 \leq C \leq 10^{500}).

输出

打印出现的次数 C 模 1000000007。

样本输入 1

1 3 2

样本输入 1 的输出

1

示例输入 2

333 334 33

样本输入 2 的输出

3

示例输入 3

0 10 0

样本输入 3 的输出

2