#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; //cout<<i<<' '<<j<<' '<<f[1][i][j]<<' '<<to[1][i][j]<<endl; } } for(int i=2;i<=18;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; //cout<<i<<' '<<j<<' '<<k<<' '<<f[i][j][k]<<' '<<to[i][j][k]<<endl; } } } }long long f1[N];int to1[N]; int v[N],d[N]; void dp2(){ for(int i=0;i<=9;i++){ int now=i;int mx=0; for(int j=18;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]); } 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 fl=0;int mx=0; int now=p[0]; for(int i=1;i<=18;i++){ int lm=v[i];if(v[i]<p[i]) lm+=10; for(int j=p[i]+1;j<=lm;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]; p[i]++; } }mx=max(mx,v[i]); if(p[i]>=10) p[i]-=10,p[i+1]+=10; }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=18;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]++; } }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]; } }void get(long long x,int *a){ for(int i=0;i<=18;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=18;i>=0;i--) res*=10,res+=p[i]; cout<<res%m; }else{ int now=0;long long res=0; for(int i=18;i>=0;i--) res*=10,res+=p[i]; now=res%m; long long x=n/m; 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=18;i>=0;i--) res*=10,res+=r[i]; cout<<res%m; } } int main(){ modify(); return 0; }