/*
TASK:string
LANG:C
*/
#include<stdio.h>
#include<string.h>
//#include<math.h>
 int pow(int a, int b)
 {
  int i=0,res=1;
  for(i=0;i<b;i++)
   res=(res*a)%1000000000;      
  return res;
 }
 
 int f(int i, int j)
 {
  int res=1;
  if(i<j)return 0;
  if(i==0 || j==0)return 0;
  if(i==j)return 1;
  if(i==1)return j;
  if(j==1)return i;
  return i*f(i-1,j-1);  
 }
 
 char S[2020],t[64];
 int n,m,p;
 int comb();
 int main()
 {
  int res=0;
  scanf("%s",&S);
  scanf("%s",&t);
  scanf("%d",&p);      
  n=strlen(S);
  m=strlen(t);  
  res=pow(m,p);      
  res-=comb();
  printf("%d\n",res);      
  return 0;      
 }
 
 int comb()
 {
  int i,j,res=0;
  for(i=0;i<n;i++)
  {
    for(j=0;j<n;j++)
    if(S[i]==S[j])break;      
    if(j!=n)break;
  }    
  if(S[i]==S[j])res--;
  int o=p-n,k=1;
  i=0;
  while(k!=0)
  {
   k=f(m-i,o-i); i++;
   res+=2*k; 
   res%=100000000;     
  }
  return res;      
 }
