数位平方和

题目描述

定义 $S(n)$ 表示 $n$ 的各个数位的 $k$ 次方的和。 定义 $H(n)$ 为满足 $H(n) \le \min\{n, H(S(n))\}$ 的最大值。 求$\sum_{i=A}^{B} H(i) \bmod (10^7 + 7)$。

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

2 1 5

输出样例 #1

14

说明

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