Time Limit : sec, Memory Limit : KB
English

## 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