#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back #define ppc __builtin_popcount using namespace std; typedef long long ll; const int maxn=1e6+10; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int dp[10][20][10]; ll DP[10][20][10],pw[20]; int nxt[10][60]; ll sm[10][60]; int f(ll n){ ll ct=0; while(n)ct=max(ct,n%10),n/=10; return ct; } void init(){ pw[0]=1;up(i,1,18)pw[i]=pw[i-1]*10; up(i,10,99){ ll val=i; while(val/10==i/10)val+=f(val),++DP[i/10][1][i%10]; dp[i/10][1][i%10]=val%10; //cout<<"! "<<i/10<<" "<<i<<" "<<DP[i/10][1][i%10]<<endl; } up(p,2,18)up(i,1,9)up(j,0,9){ int d=j; up(ct,1,10)DP[i][p][j]+=DP[max(i,ct-1)][p-1][d],d=dp[max(i,ct-1)][p-1][d]; dp[i][p][j]=d; } } ll force(ll x,ll n){ if(!n) return x; if(n<=10){ while(n--)x+=f(x); return x; } if(x<=9){ while(x<=9)x+=f(x),n--; } ll a=f(x/10),p=1,d=x%10; while(1){ if(p>=18)return 9e18; a=f(x/pw[p]),d=x%10; //cout<<"x:"<<x<<endl; //cout<<"! "<<p<<endl; bool fl=1; while(1){ if(n>=DP[a][p][d]){ x=(x/pw[p]+1)*pw[p]+dp[a][p][d]; n-=DP[a][p][d],d=dp[a][p][d]; a=f(x/pw[p]); if(x%pw[p+1]<10)break; //cout<<"now "<<x<<" "<<n<<endl; }else {fl=0;break;} } //cout<<"!!!!! "<<x<<" "<<n<<endl; if(!fl)break;p++; }return force(x,n); } void slv(){ init(); ll a=read(),m=read(),n=read()-1; if(force(a,n)<m){cout<<force(a,n);return;} ll l=0,r=n; while(l+1<r){ ll mid=l+r>>1; if(force(a,mid)<m)l=mid; else r=mid; }a=force(a,r)%m,n-=r; up(i,0,9){ if(!i){nxt[i][0]=0,sm[i][0]=1;continue;} ll l=0,r=1e16; while(l+1<r){ ll mid=l+r>>1; if(force(i,mid)<m)l=mid; else r=mid; }nxt[i][0]=force(i,r)%m,sm[i][0]=r; } up(i,1,59)up(j,0,9)nxt[j][i]=nxt[nxt[j][i-1]][i-1],sm[j][i]=min(sm[j][i-1]+sm[nxt[j][i-1]][i-1],(ll)(1e18)); while(1){ bool ok=0; down(i,59,0)if(n>=sm[a][i]){ n-=sm[a][i],a=nxt[a][i];ok=1;break; }if(!ok)break; } //cout<<"! "<<a<<" "<<n<<" "<<force(a,n)<<endl; cout<<force(a,n)%m; } int main(){ //freopen("walk.in","r",stdin); //freopen("walk.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }