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

#include <stdio.h>
#include <string.h>

#define MAXP 21
#define MAXT 2
#define MAXL 20001

char T[MAXT], curStr[MAXP];
char S[MAXL];
int P, count = 0;

void input()
{
     scanf( "%s", S );
     scanf( "%s", T );
     scanf( "%d", &P );
}

void gen( int i )
{
     if( i == P ) {
         if( strstr( curStr, S ) == NULL )
             count++;
         return;
     }
     
     curStr[i] = T[0]; gen( i + 1 );
     curStr[i] = T[1]; gen( i + 1 );
}

int main()
{
    input();
    gen( 0 );
    
    printf( "%d\n", count );
    
    return 0;
}    
    
     
