Given an integer interval `\[A, B\]` and an integer `C`, your job is to calculate the number of occurrences of `C` as string in the interval.

For example, `33` appears in `333` twice, and appears in `334` once. Thus the number of occurrences of `33` in `\[333, 334\]` is `3`.

The test case is given by a line with the three integers, `A`, `B`, `C` (`0 \leq A \leq B \leq 10^{10000}`, `0 \leq C \leq 10^{500}`).

Print the number of occurrences of `C` mod 1000000007.

1 3 2

1

333 334 33

3

0 10 0

2

Source: Japan Alumni Group Spring Contest 2013
, Japan, 2013-04-21

http://acm-icpc.aitea.net/

http://jag2013spring.contest.atcoder.jp/

http://acm-icpc.aitea.net/

http://jag2013spring.contest.atcoder.jp/