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

#include <cstdio>
#include <cmath>
#include <iostream>
#include <fstream>
#include <algorithm>

#define MAX 2048
#define in cin
#define out cout

using namespace std;

int n, m;
char a[MAX];

string str1, str2;

//ifstream(in); ofstream(out);


int recurse(int cur)
{
int i;
int ans;

if (cur == n) return 1;

ans = 0;

if (a[cur-1] != str1[0])
   {
   a[cur] = str2[0];
   ans += recurse(cur+1);
   a[cur] = str2[1];
   ans += recurse(cur+1);
   }
else
   {
   if (str2[0] != str1[1]) {a[cur] = str2[0]; ans += recurse(cur+1);}
   if (str2[1] != str1[1]) {a[cur] = str2[1]; ans += recurse(cur+1);}
   }

return ans;
}


int main(void)
{
int i, c;
int ans;

ans = 0;

//in.open("string.in"); out.open("string.out");

in >> str1 >> str2 >> n;

a[0] = str2[0];
ans += recurse(1);

a[0] = str2[1];
ans += recurse(1);

ans %= 1000000;

out << ans << endl;

return 0;
}

