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≤A≤B≤10¹⁰⁰⁰⁰, 0≤C≤10⁵⁰⁰).

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

---