import java.util.Arrays; import java.util.Scanner; public class N016 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); long x=sc.nextLong(),n=sc.nextLong(); long[] a=new long[(int)n]; for(long i=0;i=9){ while(dif>=9){ dif-=9; mem=(mem*buf)%beki; } mem=(mem*((long)Math.pow(x, dif)%beki))%beki; }else{ mem*=((long)Math.pow(x, dif)%beki); } ans=(ans+mem)%beki; cnt+=(a[i]-cnt); } System.out.println(ans); } }