# Integer in Integer

Time Limit : 8 sec, Memory Limit : 131072 KB

## B - Integer in Integer

### Problem Statement

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.

### Input

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}).

### Output

Print the number of occurrences of C mod 1000000007.

### Sample Input 1

1 3 2


### Output for Sample Input 1

1


### Sample Input 2

333 334 33


### Output for Sample Input 2

3


### Sample Input 3

0 10 0


### Output for Sample Input 3

2


Source: Japan Alumni Group Spring Contest 2013 , Japan, 2013-04-21
http://acm-icpc.aitea.net/
http://jag2013spring.contest.atcoder.jp/