/*
TASK:string
LANG:C++
*/
#include<iostream>
#include<string>
using namespace std;
    string tmp,S,T;
    int p,res;
int step(int n)
{
     long long s=T.size();
     int i;
     for(i=2;i<=n;i++)
     {
       s*=T.size();
       s%=1000000;
     }
return s%1000000;
}
bool OK()
{
     int i,j;
     for(i=0;i<=p-S.size();i++)
     {
       for(j=i;j<i+S.size();j++)
       if(tmp[j]!=S[j-i])break;
       if(j==i+S.size())return false;
     }
     return true;
}
void rec2(int pos)
{
     int i;
     if(pos==p)
     {
       if(OK()){res++;res%=1000000;}
       return;
     }
     for(i=0;i<T.size();i++)
     {
       tmp[pos]=T[i];
       rec2(pos+1);
     }
}
void rec(int pos)
{
    if(pos>=p)
    {
     if(OK())res++;
     return;
    }
    tmp[pos]=T[0];
    rec(pos+1);
    tmp[pos]=T[1];
    rec(pos+1);
}
int main()
{
    int num=1,i,j;
    cin>>S>>T>>p;
    if(T.size()<=2 && p<=20)
    {
      if(T.size()==2){rec(0);cout<<res%1000000<<"\n";}
      else cout<<"0\n";
    }
    else
    {
      if(T.size()==S.size() && T.size()==p)
      {
        cout<<step(p)-1<<"\n";
      }
      else
      {
       rec2(0);
       cout<<res<<"\n";
      }
    }
return 0;
}

