#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define popcount __builtin_popcount using namespace std; //typedef long long int ll; //typedef pair P; using ll=unsigned long long; const ll MOD=1e9+7; ll powmod(ll a, ll k){ ll ap=a, ans=1; while(k){ if(k&1){ ans*=ap; ans%=MOD; } ap=ap*ap; ap%=MOD; k>>=1; } return ans; } ll inv(ll a){ return powmod(a, MOD-2); } ll a[61], s[61], p[61]; ll solves(int k, ll r){ if(r==0) return 0; if(k==1) return 1; if(r<=a[k-1]) return solves(k-1, r); int d[4], t=0, x=k*k; ll ret=s[k-1]; while(x){ d[t]=x%10; x/=10; t++; } for(int i=0; ii) ret+=((d[t-1-i]==0)?10:d[t-1-i]); } if(r<=a[k-1]+t) return ret; else return ret+solves(k-1, r-t-a[k-1]); } ll solvep(int k, ll r){ if(r==0 || k==1) return 1; if(r<=a[k-1]) return solvep(k-1, r); int d[4], t=0, x=k*k; ll ret=p[k-1]; while(x){ d[t]=x%10; x/=10; t++; } for(int i=0; ii) (ret*=((d[t-1-i]==0)?10:d[t-1-i]))%=MOD; } if(r<=a[k-1]+t) return ret; else return ret*solvep(k-1, r-t-a[k-1])%MOD; } int main() { ll k, l, r; cin>>k>>l>>r; k=min(k, 60ull); a[1]=1, s[1]=1, p[1]=1; for(int i=2; i<=60; i++){ int x=i*i; a[i]=2*a[i-1]; s[i]=2*s[i-1]; p[i]=p[i-1]*p[i-1]%MOD; int d[4], t=0; while(x){ d[t]=x%10; x/=10; s[i]+=((d[t]==0)?10:d[t]); (p[i]*=((d[t]==0)?10:d[t]))%=MOD; t++; } a[i]+=t; } if(a[k]