/*
TASK: string
LANG: C++
*/
#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>
#include <string>
#include <set>
using namespace std;

#define MAXV 1000000
#define MAXP 2000

string t;
string s;
int p;

string strs[MAXP];
string comms[MAXP];
bool touse[MAXP];
int uni[MAXP];
bool touni[MAXP];

int main() {
    cin>>s>>t>>p;
    int ret=1;
    int i;
    for(i=0;i<p;i++) {
       ret *= t.size();
       if(ret>=MAXV)ret = ret % MAXV;              
    }
    int startret=ret;
    int j,k;
    for(i=0;i<(p-s.size()+1);i++) {
       for(j=0;j<i;j++) {
          strs[i]+='.';
       }               
       for(j=i;j<i+s.size();j++) {
          strs[i]+=s[j-i];                          
       }            
       for(j=i+s.size();j<p;j++) {
          strs[i]+='.';                          
       }
    }
    // common of the first
    int toremove=1;
    for(i=0;i<strs[0].size();i++) {
       if(strs[0][i]=='.') {
          toremove *= t.size();
          if(toremove >= MAXV) toremove = toremove % MAXV;                    
       }                              
    }
    toremove *= (p-s.size()+1);
    if(toremove>=MAXV)toremove = toremove % MAXV;
    //ret -= toremove;
    //if(ret<0)ret+=MAXV;
    int currtoremove;
    /*for(i=1;i<(p-s.size()+1);i++) {
       currtoremove=toremove;
       for(j=i-1;j>=0;j--) {
           touse[j]=1;
           for(k=0;k<strs[0].size();k++) {
               if(strs[i][k]!=strs[j][k] && strs[i][k]!='.' && strs[j][k]!='.') {
                   touse[j]=0;
                   break;                          
               }         
               else if(strs[i][k]=='.' && strs[j][k]=='.') {
                   comms[j]+='.'; 
               }                 
               else if(strs[i][k]==strs[j][k]) {
                   comms[j]+=strs[i][k];  
               }    
               else if(strs[i][k]!='.') {
                   comms[j]+=strs[i][k]; 
               }
               else comms[j]+=strs[j][k];
           }                
       }                           
    }*/
    for(i=0;i<(p-s.size()+1);i++) {
       if(i==0) {
           continue;         
       }
       currtoremove=1;
       for(j=i-1;j>=0;j--)touse[j]=1;
       for(j=i-1;j>=0;j--) {
           for(k=0;k<strs[0].size();k++) {
               if(strs[i][k]!=strs[j][k] && strs[i][k]!='.' && strs[j][k]!='.') {
                  touse[j]=0;
                  break;                       
               }                          
           }                
       }
       for(k=0;k<strs[0].size();k++) {  
             if(strs[i][k]=='.') {
                set<char> ss;
                bool b=true;
                for(j=i-1;j>=0;j--) {
                    if(strs[j][k]!='.' && touse[j])ss.insert(strs[j][k]);
                    else if(touse[j]){
                        b=false;break; 
                    }                
                }           
                if(b){  
                   if(ss.size()==0){currtoremove *= t.size();}
                   else currtoremove*=ss.size();
                   if(currtoremove >= MAXV)currtoremove = currtoremove % MAXV;   
                }
                else {
                    currtoremove *= t.size();
                    if(currtoremove >= MAXV) {
                       currtoremove = currtoremove % MAXV;               
                    } 
                }
             }
             else {
                  bool b=false;
                  bool bb=true;
                  for(j=i-1;j>=0;j--) {
                      if(touse[j])bb=false;
                      if(strs[j][k]==strs[i][k] && touse[j]){b=true;break;}
                      if(strs[j][k]=='.' && touse[j]){b=true;break;}                
                  }
                  if(bb) {
                       currtoremove=0;  
                  }
                  else if(!b) {
                      currtoremove=0;  
                  }
             }                        
       }
       toremove -= currtoremove;
       if(toremove<0)toremove+=MAXV;   
       //int x=toremove-currtoremove;
       //cout<<x<<endl;
       //if(x<0)x+=MAXV;        
       //ret -= x;
       //if(ret<0)ret+=MAXV; 
    }
    //ret = startret-ret;
    //if(ret<0)ret=MAXV;
    //cout<<toremove<<endl;
    ret-=toremove;
    if(ret<0)ret+=MAXV;
    cout<<ret<<endl;
    //cin>>i;
    return 0;
}
