Your task is to calculate the sum (indicated by S) of all the k-balanced integers between [L, R]. An integer is called k-balanced when either of #1 or #2 below holds true.

The length of the integer <= k
Sum of the first k digits (with no leading zeros) is equal to the sum of the last k digits.

Input format

L R k

Output format

S % 1000000007

Constraints

0 < L <= R < 10^18

0 < k <= 18

Sample Input

9 23 1

Sample Output

42

Explanation

9, 11 and 22 are the only 3 integers between 9 and 23 ( both included ) that are k-balanced. Hence, the answer is 9+11+22=42

见题面

见题面