#include #include #include #include #include #include #include #include #include //#include using namespace std; typedef long long int llint; typedef int beet; #define ween tuple #define mp make_pair #define mt make_tuple #define pub push_back #define puf push_front #define pob pop_back #define pof pop_front #define izryt bool #define fir first #define sec second #define res resize #define ins insert #define era erase const llint mod=1000000007; const llint big=1e9+1e8; const llint red=0xE869120; const llint pro=1002001; vector> memo; tuple solve(llint in,llint f){ //F(f)のin文字目未満を求める //和,積,文字数を返す tupleT; deque st;// f^2を文字列化 llint ff=f*f; if(memo[f]!=mt(-1,-1,-1)&&get<2>(memo[f])<=in){return memo[f];} llint wa=0,sek=1,moz=0; if(f==1){ if(in<=0){return mt(0,1,0);} else{return mt(1,1,1);} } T=solve(in,f-1); if(in<=get<2>(T)){return T;} wa=get<0>(T);sek=get<1>(T);moz=get<2>(T); llint i=0; while(ff>0){st.puf(ff%10);ff/=10;if(st.front()==0){st.front()+=10;}} for(i=0;i=in){return mt(wa,sek,moz);} } T=solve(in-moz,f-1); wa+=get<0>(T);wa%=mod; sek*=get<1>(T);sek%=mod; moz+=get<2>(T); if(moz T,Y; for(i=0;i<70;i++){memo[i]=mt(-1,-1,-1);} cin>>k>>l>>r;l--; k=min(k,(llint)64); T=solve(r,k); Y=solve(l,k); if(r>get<2>(T)){cout<<-1<(T)-get<0>(Y)+mod)%mod; ansb=1;llint kr=mod-2;gen=get<1>(Y); while(kr>0){ if(kr%2==1){ansb*=gen;}ansb%=mod; kr/=2; gen*=gen;gen%=mod; } ansb*=get<1>(T);ansb%=mod; cout<