Step 1：
“定义 \(S(n)\) 表示 \(n\) 个的各个数位的 \(k\) 次方的和。”
数位的 \(k\) 次方，我们可以通过快速幂求出，为了节省时间，我们可以定义一个 \(a\) 数组，来表示 \(0\sim9\) 区间中各数字 \(k\) 次方的值。
然后我们通过定义一个 \(s\) 数组来存储 \(0\sim4\times10^{6}\) 区间中各数字的 \(S\) 值。
Step 2：
“定义 \(H(n)\) 为满足 \(H(n) \le \min\{n, H(S(n))\}\) 的最大值。“
关于这个，不难想到通过递归求出 \(H(n)\) 的值。
但是，进行手动模拟后不难发现，有些时候直接将 \(H(i)=\min{n,H(S(i))}\) 会造成死循环。
例子：当 \(k=2\)，\(n=2\) 时，求 $ H(2)$ 即求 $ H(4) \Rightarrow H(16) \Rightarrow H(37) \Rightarrow H(58) \Rightarrow H(89) \Rightarrow H(145) \Rightarrow H(42) \Rightarrow H(20) \Rightarrow H(4) \Rightarrow H(16) \dots $
显然，这形成了一个环，此时不难想到“环上最小值就是整个环相同 \(H\)。”
所以我们可以通过定义一个 \(mark\) 数组来表示个点的访问次数，若 mark[i]==2 则说明出现了环，那你就再走一次去寻找并更新环上最小值。
这时不难想到通过定义一个 \(h\) 数组来实现记忆化搜索，又省了一些时间。
Step 3：
此时你会发现题目已经做完，剩下仅需处理一些细节同时略微整合一下代码便可以 \(\color{black}\texttt{AC}\) 了。
//written by naught
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<climits>
using namespace std;
typedef long long ll;
#define Maxn 4000005 //4倍空间
#define Mod 10000007
inline ll read(ll x=0,bool f=0,char c=getchar()){while(!isdigit(c))f=c=='-',c=getchar();while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();return f?-x:x;}
ll k,A,B,m;
ll ans;
ll a[12],s[Maxn],h[Maxn],mark[Maxn];
ll hts(ll x,ll y) //快速幂
{
m=1;
while(y)
{
if(y%2==1)
{
m*=x;
m%=Mod;
}
x*=x;
x%=Mod;
y/=2;
}
return m;
}
ll S(ll x) //求S
{
m=0;
while(x)
{
m+=a[x%10];
m%=Mod;
x/=10;
}
return m;
}
ll H(ll x) //求H
{
if(h[x]) return h[x]; //记忆化搜索
if(mark[x]==2) return x;
++mark[x];
h[x]=min(x,min(s[x],H(s[x]))); //处理环
--mark[x];
return h[x];
}
int main()
{
k=read(),A=read(),B=read();
for(ll i=0;i<10;++i){
a[i]=hts(i,k);
}
for(ll i=0;i<Maxn;++i){
s[i]=S(i);
}
h[0]=0;
h[1]=1;
for(ll i=A;i<=B;++i){
ans+=H(i);
ans%=Mod; //勿忘取模
}
printf("%lld",ans);
return 0;
}