/*
TASK:string
LANG:C++
*/
#include <iostream>
#include <string.h>
using namespace std;
char a[2048],b[2048];
int p,N,M;
int P[2048];
void fillP()
{
     P[1]=M;
     if(N==1) P[1]--;
     for(int i=2;i<N;i++)
             P[i]=P[i-1]*M;
             
     for(int i=N;i<=p;i++)
     {  
             P[i]=P[i-1]*M-1;
             if(P[i]>1000000) P[i]%=1000000;
     }
}
             
int main()
{
    cin>>a;
    cin>>b;
    cin>>p;
    N=strlen(a);
    M=strlen(b);
    fillP();
    cout<<P[p]<<endl;
    
  //  system("PAUSE");
}
    
