$(function(){document.getElementById("fixed-server-timer").style.display = "none";})

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 Name

Japan Alumni Group Spring Contest 2013