using System; using System.Collections.Generic; using System.Collections; using System.Collections.Specialized; using System.Linq; using System.Text; using System.IO; using System.Reflection; using static System.Math; using System.Numerics; using System.Threading; using System.Runtime.CompilerServices; using System.Diagnostics; static class Program{ const int mod=(int)1e9+7; static void Main(){ Sc sc=new Sc(); var s=sc.La; var h=new long[93]; h[0]=0;h[1]=1; var lik=new List(); for(int i = 2;i=s[1]&&h[i]<=s[2]){ var t=h[i].ToString(); var bo=true; for(int j = 0;j[s[0]+2]; for(int i = 0;i<=s[0]+1;i++) {dp[i]=new Dictionary();} dp[0].Add(0,1); for(int i = 0;i<=s[0];i++) { foreach(var e in dp[i]){ if(ac.h[e.Key].stl.Count!=0){ ans-=e.Value*Fp(10,s[0]-i); continue; } for(int j = 0;j<10;j++) { var d=ac.Av(ac.h[e.Key],(char)('0'+j)); if(dp[i+1].ContainsKey(d.Item1.n)){dp[i+1][d.Item1.n]+=e.Value;} else{dp[i+1].Add(d.Item1.n,e.Value);} } } } Console.WriteLine(ans); } static long Fp(long x,long e){ long r=1; while(e>0){ if((e&1)>0){r*=x;r%=mod;} x=(x*x)%mod; e>>=1; } return r; } } public class Ac{ static private int o; public int n,cnt=1; public Nd root; public Nd[] h; public Nd[] q; public class Nd{ public Nd[] ar; public List li=new List(); public Nd sx; public List stl=new List(); public int c,f=0,n; public bool b=false; public Nd(int c,int f){this.c=c-o;this.f=f;} public override string ToString(){ var t="n:"+n.ToString("d2")+" f:"+f.ToString()+" c:"+(char)(c+o)+" pr:"+(sx==null?0:sx.n).ToString("d2")+" "+li.Count.ToString("d2")+":"; Nd g=this;while(g.ar==null){g=g.sx;} for(int j=0;j(); for(int i = 0;i0){ var e=qu.Dequeue(); for(int i = 0;i0){e.li[i].stl.AddRange(e.li[i].sx.stl);} if(e.li[i].b){qu.Enqueue(e.li[i]);} e.li[i].n=p; h[p]=e.li[i]; } } if(h.Length==1){ h[0].ar=new Nd[n]; for(int i = 0;i f){ var e=root; for(int i = 0;i f){ var e=root; for(int i = 0;i0){ long t=a/b; a-=t*b;(a,b)=(b,a); u-=t*v;(u,v)=(v,u); } u%=mod; if(u<0){u+=mod;} return u%mod; } } static class Ex{ static public int[] Za1(string s,int n){ var a=new int[s.Length]; for(int i=n+1,j=0;i=0;){ while(i-j>=0&&s[n-j]==s[i-j]){j++;} a[i]=j; if(j==0){i--;continue;} int k=1; while(i-k>=0&&k+a[n-k]=0&&i+j=0&&i+k(int n,Func f){var a=new T[n];for(int i=0;i(int n,Func f){var a=new T[n];for(int i=0;i(int n,Func f){var a=new T[n];for(int i=0;i(int n,Func f){var a=new T[n];for(int i=0;i