Sum of Minimal Chain Values

Given three integers A, B and k, define the function \(S(n)\) as the sum of the \(k\)th powers of the digits of \(n\):

\( S(n)=\sum_{d\in digits(n)} d^k \)

Now, define \(H(n)\) via the recurrence relation

[ H(n)=\min{n, H(S(n))} ]

In other words, consider the sequence \(a_0=n,\; a_{i+1}=S(a_i)\). Since this sequence will eventually repeat, define \(H(n)\) as the minimum value encountered in this chain.

Your task is to compute

[ \sum_{i=A}^{B} H(i) \bmod (10^7+7), ]

where \(10^7+7=10000007\).

inputFormat

The input consists of a single line containing three space‐separated integers: A, B and k.

\(1 \le A \le B \le 10^5\) and \(1 \le k \le 10\) (the constraints are such that a simulation for each number is feasible).

outputFormat

Output a single integer: the value of \(\sum_{i=A}^{B} H(i) \bmod (10^7+7)\).

sample

1 10 2

46