Description

Define $S(n)$ as the sum of the $k$-th powers of the digits of $n$.

Define $H(n)$ as the maximum value satisfying $H(n) \le \min\{n, H(S(n))\}$.

Compute $\sum_{i=A}^{B} H(i) \bmod (10^7 + 7)$.

Input Format

One line with three integers $k, A, B$.

Output Format

One integer, equal to $\sum_{i=A}^{B} H(i) \bmod (10^7 + 7)$.

2 1 5

14

Hint

For $20\%$ of the testdata, $A, B \le 50$. For $100\%$ of the testdata, $1 \le A, B \le {10}^6$, $1 \le k \le 6$.

Translated by ChatGPT 5