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

#include <stdio.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <bits/basic_string.tcc>
using namespace std;

bool nam(int r,string c, string v)
{
    for (int i=0;i<r-1;i++)
    {
    if (c[i]==v[0]&&c[i+1]==v[1])
    return true;
    };
    return false;
}

string s,t;
char y;
int p;
long int br=0;
int mat[2001];
string x;
main()
{
    cin>>s;
    cin>>t;
    cin>>p;
    int u;
    if (t.size()==1) {cout<<0;return 0; }
    for(int i=0;i<p+1;i++)
    {
        for (int j=0;j<p;j++) mat[j]=0;
        for (int j=p-1;j>p-1-i;j--) mat[j]=1;
        for (int j=0;j<p;j++) x[j]=t[mat[j]];
        do
        {    
        for (int j=0;j<p;j++) x[j]=t[mat[j]];
       // for (int j=0;j<p;j++) cout<<x[j];
        //cout<<endl;
        //cout<<x.find(s,0)<<endl;
        if (!nam(p,x,s)) {br++;if (br>=1000000) br=br%1000000;}
        }
        while (next_permutation(mat,mat+p));
      
       /* }
        while (u<p-i);
        
        /*if (i!=0&&i!=p)
        {y=x[p-1];
        x[p-1]=x[p-2];
        x[p-2]=y;
        if (x.find(s,0)>=p||x.find(s,0)<0) {br++;if (br>=1000000) br=br%1000000;}
        for (int j=0;j<p;j++) cout<<x[j];
        cout<<endl;
        };*/
        
    };
    cout<<br<<endl;
}
