시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 128 MB 13 6 6 54.545%

문제

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 ≤ A ≤ B ≤ 1010000, 0 ≤ C ≤ 10500).

 

출력

Print the number of occurrences of C mod 1000000007.

 

예제 입력

1 3 2

예제 출력

1

예제 입력 2

333 334 33

예제 출력 2

3

예제 입력 3

0 10 0

예제 출력 3

2

힌트