#include using namespace std; using ll = long long; //const ll mod = 998'244'353; const ll mod = 1'000'000'007; //const ll mod = 67'280'421'310'721; struct mint{ long long x; mint(long long x=0):x((x%mod+mod)%mod){} mint operator-() const{ return mint(-x); } mint& operator+=(const mint& a){ if((x+=a.x)>=mod)x-=mod; return *this; } mint& operator-=(const mint& a){ if((x+=mod-a.x)>=mod)x-=mod; return *this; } mint& operator*=(const mint& a){ (x *= a.x) %= mod; return *this; } mint operator+(const mint& a) const{ mint res(*this); return res+=a; } mint operator-(const mint& a) const{ mint res(*this); return res-=a; } mint operator*(const mint& a) const{ mint res(*this); return res*=a; } mint pow(long long n) const { assert(0 <= n); mint a = *this, r = 1; while (n) { if (n & 1) r *= a; a *= a; n >>= 1; } return r; } mint inv() const{ return pow(mod-2); } mint& operator/=(const mint& a){ return (*this)*=a.inv(); } mint operator/(const mint& a) const { mint res(*this); return res/=a; } friend ostream& operator<<(ostream& os, const mint& m){ os << m.x; return os; } bool operator==(const mint& a) const { return x == a.x; } bool operator<(const mint& a) const{ return x < a.x; } }; ll k,l,r; vector len,sum; vector mul; void calc(ll now){ ll w = now * now; ll s = 0; ll le = 0; mint m = 1; while(w){ ll a = w % 10; w /= 10; if(a==0) a = 10; le++; s += a; m *= mint(a); } le += 2 * len[now-1]; s += 2LL * sum[now-1]; m *= mul[now-1] * mul[now-1]; len.push_back(le); sum.push_back(s); mul.push_back(m); if(le c(ll m,ll a){ if(a==0) return make_pair(0LL,mint(1)); if(m==1){ assert(a==1); return make_pair(sum[m],mul[m]); } if(len[m-1]>=a) return c(m-1,a); ll l = len[m-1]; ll b = len[m] - 2*len[m-1]; if(l+b<=a){ pair now = make_pair(sum[m]-sum[m-1],mul[m]*(mul[m-1].inv())); pair nxt = c(m-1,a-l-b); return make_pair(now.first+nxt.first,now.second*nxt.second); }else{ pair now = make_pair(sum[m-1],mul[m-1]); vector use; ll w = m * m; while(w){ ll mm = w % 10; w /= 10; if(mm==0) mm = 10; use.push_back(mm); } reverse(use.begin(),use.end()); for(int i = 0;i solve(ll a){ ll mx = len.size()-1; return c(mx,a); } int main(){ cin>>k>>l>>r; len.push_back(0); sum.push_back(0); mul.push_back(1); calc(1); ll mx = len.size()-1; if(mx>k){ cout<<-1< L = solve(l-1); pair R = solve(r); cout<