/*
TASK:string
LANG:C++
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>


using namespace std;
void input();
void solve();
void rec(int pos);
void check();

char S[1024];
char T[1024];
char x[1024];

int N;
int L;
int count = 0;

int main()
{
input();
solve();

return 0;
}

void solve()
{
if(strlen(T) != 2) { printf("0\n"); return; }
L = strlen(S);
rec(0);
printf("%d\n", (1<<N) - count);
}


void rec(int pos)
{
if(pos == N) { check(); return; }

x[pos] = T[0];
rec(pos+1);
x[pos] = T[1];
rec(pos+1);
}


void check()
{
int i, j;
for(i = 0; i <= N - L; i++)
      {
      for(j = 0; j < L; j++)
            if(x[i+j] != S[j]) break;
      if(j == L) { count++; return; }
      }
}

void input()
{
char n[10];
gets(S);
gets(T);
gets(n);
N = atoi(n);
}

