Description

定义 $S(n)$ 表示 $n$ 的各个数位的 $k$ 次方的和。

定义 $H(n)$ 为满足 $H(n) \le \min\{n, H(S(n))\}$ 的最大值。

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

Input Format

一行三个数 $k, A, B$。

Output Format

一个数，表示 $\sum_{i=A}^{B} H(i) \bmod (10^7 + 7)$。

2 1 5

14

Hint

对于 $20\%$ 的数据，$A, B \le 50$。
对于 $100\%$ 的数据，$1 \le A, B \le {10}^6$，$1 \le k \le 6$。