/*
TASK:string
LANG:C++
*/

#include <iostream>
#include <string>
#include <cmath>
using namespace std;

typedef unsigned long long int ulli;

int const MOD=1000000;
char s[2002];
char t[2002];
char pp[2002];
int P,lt,ls;
ulli hs,hp,r,al;

ulli pw(ulli x,ulli y){
     ulli rr=1;
     int i;
     for(i=1;i<=y;i++) rr=(rr*(x%MOD))%MOD;
     return rr;
}

void rec(int w){
     int k;
     if(w==P) return; 
     for(k=0;k<lt;k++){
           hp+=(pp[w]*t[k]);  
           if(w>=ls) hp-=(pp[w-ls+1]*pp[w-ls+2]);
           if(hp!=hs){  pp[w+1]=t[k]; rec(w+1); }
           else{ r=(r+(pw(lt,P-w-1))%MOD)%MOD; }
           hp-=(pp[w]*t[k]); 
           if(w>=ls) hp+=pp[w-ls+1]*pp[w-ls+2];
     }
}


int main()
{
    int i;
    cin>>s>>t>>P;
    lt=strlen(t); ls=strlen(s);
    for(i=0;s[i+1];i++) hs+=s[i]*s[i+1];
    for(i=0;t[i];i++)
    {
      pp[1]=t[i];
      rec(1);
    }
    cout<<(pw(lt,P)%MOD-r%MOD)%MOD<<endl;
    return 0;
}
