#include using namespace std; #define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++) #define rep(i,n) repl(i,0,n) #define mp(a,b) make_pair((a),(b)) #define pb(a) push_back((a)) #define all(x) (x).begin(),(x).end() #define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x)) #define fi first #define se second #define dbg(x) cout<<#x" = "<<((x))< ostream& operator<<(ostream& o, const pair &p){o<<"("< ostream& operator<<(ostream& o, const vector &v){o<<"[";for(T t:v){o<0){ if(n&1) res=res*x%p; x=x*x%p; n>>=1; } return res; } long mod_inv(long x, long p=MOD){ return mod_pow(x%p, p-2, p); } #define LIM 61 long len[LIM],add[LIM],mul[LIM]; vector Nstr[LIM]; // i*i を桁ごと // n*nの桁数返し,nの桁のaddとmulも計算 long num(int n, long *a, long *m, long maxL=INF){ long l = 0; *a = 0; *m = 1; for(auto d : Nstr[n]){ if(l>=maxL) return l; *a += d; *m *= d; l++; } return l; } // 1からx桁目までの和と積 pair calc(long x){ long a=0, m=1; while(x>0){ int idx = upper_bound(len, len+LIM, x) - len; idx--; a = (a + add[idx]); m = (m * mul[idx])%MOD; x -= len[idx]; long p,q,r; p = num(idx+1, &q, &r, x); a = a+q; m = (m*r)%MOD; x -= p; } return mp(a,m); } int main(){ long k,l,r; cin>>k>>l>>r; l--; repl(i,1,LIM){ long x = i*i; while(x>0){ long d = x%10; if(d==0) d=10; Nstr[i].pb(d); x /= 10; } reverse(all(Nstr[i])); } len[0]=0; add[0]=0; mul[0]=1; repl(i,1,LIM){ long ll,a,m; ll = num(i, &a, &m); len[i] = len[i-1]*2+ll; add[i] = add[i-1]*2+a; mul[i] = (mul[i-1]*mul[i-1]%MOD * m)%MOD; } if(k