/*
TASK:string
LANG:C
*/
#include <string.h>
#include <stdio.h>
char s[2000];
char t[2] , s[2000];
int p , len;
long int count = 0 ;
enum mytype { one , two } str[1060900][20] ,s1[2000] , tempstr[20];
void myf ( int stage )
{int j ;

if ( stage < p ) {
         tempstr[stage] = 0 ; myf(stage+1);
         tempstr[stage] = 1 ; myf(stage+1);}
else { for (j=0;j<p;j++) str[count][j] = tempstr[j] ;
      count++ ;}
}
int main(void)
{

long int k,l,m,i;
scanf("%s",s);
scanf("%s",t);
len = strlen(s); 
scanf("%d",&p);
 for ( i=0 ;i < len ; i++) if ( s[i] == t[0] ) s1[i] = 0;
                          else s1[i] = 1 ;
 myf(0);
 if ( len > 2 ) printf ("%ld",count);
 else {m=count-1;
      for (k=0;k<m;k++)
          for (l=0;l<p;l++)
              if (str[k][l] == s1[0]) 
                 if (str[k][l+1] == s1[1] ) count--;
      printf ("%ld",count);}
                  
 
scanf("%s",s);
  return 0;
}
