/*
TASK: string
LANG: C++
*/
#include<iostream>
#include<string>
using namespace std;
int a[50],P,ans=0;
string S,T;
bool check()
{
    int i,j;
    bool f;
    for(i=0;i<P-S.length()+1;i++)
    {
        if(T[a[i]]==S[0])
        {
            f=true;
            for(j=i+1;j<i+S.length();j++)
                if(T[a[j]]!=S[j-i])
                {
                    f=false;
                    break;
                }
            if(f)return true;
        }
    }
    /*for(i=0;i<P;i++)cout<<T[a[i]];
    cout<<'\n';*/
    return false;
}
void gen(int s,int i)
{
    a[i]=s;
    if(i==P-1)
    {
        if(!check())++ans;
        ans%=1000000;
        return;
    }
    gen(0,i+1);
    gen(1,i+1);
}
int main()
{
    cin>>S>>T>>P;
    if(P<=S.length())
    {
        ans=1;
        for(int i=0;i<P;i++)
        {
            ans*=T.length();
            ans%=1000000;
        }
        if(P==S.length())ans--;
        if(ans==-1)ans=999999;
        else ans%=1000000;
        return 0;
    }
    gen(0,0);
    gen(1,0);
    cout<<ans<<'\n';
    return 0;
}
