/*
TASK:string
LANG:C++
*/
#include <iostream>
#include <string>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
string a,b,res;
int n,br=0,k;
void solve2()
{
    map<char,int>r;
    int i;
    for(i=0;i<b.size();i++)r[b[i]]=1;
    
    for(i=0;i<a.size();i++)if(r[a[i]]==1){cout<<55<<endl;return;}
    cout<<(int)pow((double)n,(double)n)%1000000<<endl;return;
    
    
}
void solve(int pos)
{
//cout<<pos<<endl;
if(pos==n){br++;return;}
int i;
for(i=0;i<b.size();i++)
{
    
    res[pos]=b[i];//cout<<res[pos]<<endl;
 // if(pos>=k-1)cout<<" ->"<<res.substr(pos-k+1,k)<<endl;
    if(pos>=k-1){if(res.substr(pos-k+1,k)!=a)solve(pos+1);}
    else
    solve(pos+1);
}

}
int main()
{
    cin>>a>>b;
  int i;
  //cout<<a<<b<<endl;
  cin>>n;
  k=a.size();
  for(i=0;i<=n+3;i++)
    res+='a';
 if(b.size()>2||n>20)solve2();
 else
    {solve(0);
     cout<<br<<endl;
    }
    return 0;

}
