/*
TASK:string
LANG:C++
*/
#include<iostream>
#include<cstring>
using namespace std;
int vt[53],vs[53];
int main()
{
 char s[2002],t[55];
 long n,m=1000000,ls=-1,lt=-1,i,j,d,cs=0,ct=0;
 cin>>s>>t>>n;
 while(s[++ls]!='\0')
 {
  if(s[ls]>='A'&&s[ls]<='Z')vs[s[ls]-'A']=1;
  else vs[s[ls]-'a'+26]=1;
 }
 while(t[++lt]!='\0')
 {
  if(t[lt]>='A'&&t[lt]<='Z')vt[t[lt]-'A']=1;
  else vt[t[lt]-'a'+26]=1;
 }
 
 for(i=0;i<52;i++)
 {
  if(vs[i])cs++;
  if(vt[i])ct++;
 }
 
 for(i=0;i<52;i++)
  if(vs[i]==1&&vt[i]==0)break;

 d=lt;
 for(j=1;j<n;j++)
 {
  d*=lt;
  if(lt>m)lt%=m;
 }
 
 if(i==52)
 {
  if(ls==n&&cs==1)
  {
   d--;
  }
  if(ls==1&&i==52)
  {
   if(ct==1)d=0;
   else d=1;
  }
 }
 
 if(cs==1&&ct==2&&i==52&&n==3)d=5;
 
 cout<<d<<'\n';
 //system("pause");
 return 0;
}
