/*
TASK:string
LANG:C++
*/
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string>
#include<stdio.h>
using namespace std;
#define MN 2002
long mod=1000000;
long n,m,l;
string a,b;
long q[MN];
long p[MN];
void solve()
{
    long i,j,lamp=0;
    cin>>a>>b>>n;
    m=b.size();
    l=a.size();
    p[0]=1;
    q[l]=1;
    q[l+1]=m+m;
    for(i=1;i<=n;i++)
    {
       p[i]=p[i-1]*m;
    }
    for(j=1;j<l;j++)
        if(a[j-1]!=a[j])
            lamp=1;
    if(!lamp)
        q[l+1]-=m-1;
    for(i=l+2;i<=n;i++)
    {
        if(!lamp)
        q[i]=(q[i-1]*m+m)%mod;
        else
        q[i]=(q[i-1]*m+m)%mod;
    }
    cout<<abs(p[n]-q[n])%mod<<endl;
}
int main()
{
    solve();
    //system("pause");
    return 0;
}
