#include<bits/stdc++.h> #define pii pair<int,int> #define fi first #define se second #define mk make_pair #define clz __builtin_clzll using namespace std; const int N=22; long long f[N][N][N];int to[N][N][N]; long long a,m,n; pii calc(int mx,int d){ int step=0; while(1){ d+=max(d,mx);step++; if(d>=10) break; }d%=10;return mk(step,d); } void dp(){ for(int i=0;i<=9;i++){ for(int j=0;j<=9;j++){ if(i==0&&j==0) continue; pii tmp=calc(i,j); f[1][i][j]=tmp.fi;to[1][i][j]=tmp.se; } } for(int i=2;i<=19;i++){ for(int j=0;j<=9;j++){ for(int k=0;k<=9;k++){ int now=k; if(j==0&&k==0) continue; for(int st=1;st<=10;st++){ f[i][j][k]+=f[i-1][max(j,st-1)][now]; now=to[i-1][max(j,st-1)][now]; }to[i][j][k]=now; } } } }long long f1[N];int to1[N]; int v[N],d[N]; void dp2(){ for(int i=1;i<=9;i++){ int now=i;int mx=0; for(int j=19;j>=1;j--){ for(int k=1;k<=v[j];k++){ f1[i]+=f[j][max(mx,k-1)][now]; now=to[j][max(mx,k-1)][now]; }mx=max(mx,v[j]); }if(max(mx,now)==0) continue; while(now<v[0]) f1[i]++,now+=max(mx,now); to1[i]=now-v[0]; } }int p[N]; void try_move(long long &step){ int mx=0,mx2=0; int now=p[0];int fl=1; for(int i=1;i<=19;i++){ int lm=v[i];if(v[i]<p[i]) lm+=10; mx2=0;for(int j=i+1;j<=19;j++) mx2=max(mx2,p[j]); int flag=1;for(int j=i+1;j<=19;j++) if(p[j]!=v[j]) flag=0; if(flag) break; if(now==0&&max(mx,mx2)==0&&p[i]==0) continue; for(int j=p[i]+1;j<=10;j++){ if(j>=11) mx2=max(mx2,p[i+1]+1); if(f[i][max(max(mx,mx2),(j-1)%10)][now]<=step){ step-=f[i][max(max(mx,mx2),(j-1)%10)][now]; now=to[i][max(max(mx,mx2),(j-1)%10)][now]; p[i]++; }else{ break; } } if(p[i]>=10) p[i]-=10,p[i+1]++; for(int j=i+1;j<=19;j++) if(p[j]>=10) p[j]-=10,p[j+1]++; mx=max(mx,p[i]); }mx=0; for(int i=19;i>=1;i--){ int lm=v[i];if(v[i]<p[i]) lm+=10; mx2=0;for(int j=i+1;j<=19;j++) mx2=max(mx2,p[j]); if(now==0&&max(mx,mx2)==0&&p[i]==0) continue; for(int j=p[i]+1;j<=v[i];j++){ if(j>=11) mx2=max(mx2,p[i+1]+1); if(f[i][max(max(mx,mx2),(j-1)%10)][now]<=step){ step-=f[i][max(max(mx,mx2),(j-1)%10)][now]; now=to[i][max(max(mx,mx2),(j-1)%10)][now]; p[i]++; }else{ break; } } if(p[i]>=10) p[i]-=10,p[i+1]++; for(int j=i+1;j<=19;j++) if(p[j]>=10) p[j]-=10,p[j+1]++; mx=max(mx,p[i]); if(p[i]!=v[i]) fl=0; }for(int i=1;i<=19;i++) if(p[i]!=v[i]) fl=0; if(!fl){ mx=0,mx2=0; int mxps=0,fla=1; for(int i=1;i<=19;i++){ int lm=v[i]; mx2=0;for(int j=i+1;j<=19;j++) mx2=max(mx2,p[j]); if(now==0&&max(mx,mx2)==0&&p[i]==0) continue; for(int j=p[i]+1;j<=10;j++){ if(f[i][max(max(mx,mx2),(j-1)%10)][now]<=step){ step-=f[i][max(max(mx,mx2),(j-1)%10)][now]; now=to[i][max(max(mx,mx2),(j-1)%10)][now]; p[i]++; }else{ break; } } if(p[i]>=10) p[i]-=10,p[i+1]++; for(int j=i+1;j<=19;j++) if(p[j]>=10) p[j]-=10,p[j+1]++; mx=max(mx,p[i]); if(p[i]==0&&fla) mxps=i;else fla=0; }mx=0,mx2=0;for(int i=mxps;i>=1;i--){ int lm=v[i]; mx2=0;for(int j=i+1;j<=19;j++) mx2=max(mx2,p[j]); if(now==0&&max(mx,mx2)==0&&p[i]==0) continue; for(int j=p[i]+1;j<=10;j++){ if(f[i][max(max(mx,mx2),(j-1)%10)][now]<=step){ step-=f[i][max(max(mx,mx2),(j-1)%10)][now]; now=to[i][max(max(mx,mx2),(j-1)%10)][now]; p[i]++; }else{ break; } } if(p[i]>=10) p[i]-=10,p[i+1]++; for(int j=i+1;j<=19;j++) if(p[j]>=10) p[j]-=10,p[j+1]++; mx=max(mx,p[i]); }mx=0; for(int i=1;i<=19;i++) mx=max(mx,p[i]); while(step>0) now+=max(mx,now),step--; } p[0]=now; while(now<v[0]&&step>0) now+=max(mx,now),step--; p[0]=now; }long long F[N][N<<2];int To[N][N<<2]; int r[N]; void try_move2(int now,long long &step){ int mx=0; for(int i=19;i>=1;i--){ for(int j=1;j<=10;j++){ if(f[i][max(mx,j-1)][now]<=step){ step-=f[i][max(mx,j-1)][now]; now=to[i][max(mx,j-1)][now]; r[i]++; }else{ break; } }mx=max(mx,r[i]); } while(step>0) step--,now+=max(mx,now); r[0]=now; }void incr(){ for(int i=0;i<=9;i++) To[i][0]=to1[i],F[i][0]=f1[i]; for(int j=1;j<=61;j++){ for(int i=0;i<=9;i++) F[i][j]=F[i][j-1]+F[To[i][j-1]][j-1],To[i][j]=To[To[i][j-1]][j-1]/*,cout<<i<<' '<<j<<' '<<To[i][j]<<endl*/; } }void get(long long x,int *a){ for(int i=0;i<=19;i++){ a[i]=x%10;x/=10; } } void modify(){ cin>>a>>m>>n; get(m,v);get(a,p); dp();dp2();incr(); n--; try_move(n); if(n==0){ long long res=0; for(int i=19;i>=0;i--) res*=10,res+=p[i]; cout<<res%m; }else{ int now=0;long long res=0; for(int i=19;i>=0;i--) res*=10,res+=p[i]; now=res%m; long long x=n/((m+9)/10); int lm=65-clz(x); for(int i=lm;i>=0;i--){ if(now==0) break; if(F[now][i]<=n){ n-=F[now][i];now=To[now][i]; } }if(now==0){ cout<<0;return; } try_move2(now,n); res=0;for(int i=19;i>=0;i--) res*=10,res+=r[i]; cout<<res%m; } } int main(){ modify(); return 0; }