/*
TASK: string
LANG: C++
*/
#include<iostream.h>
#include<string.h>
char s[20],t[20];
unsigned p;
unsigned long n;
int main()
{
cin>>s>>t>>p;
int i;n=1;
for (i=1;i<=p;i++)
n=n*strlen(t);
n--;
if (p==strlen(s))
cout<<n%1000000;
if (strlen(s)==1)
cout<<1;
cin>>p;
}
