/*
TASK:string
LANG:C++
*/
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int T[60],P[2001],n,br,br2;
char s[2000];
char t[2000];
void vhod()
{scanf("%s",&s);
 scanf("%s",&t);
 int y=strlen(t);
 int u=1;
 for(int i=0;i<y;i++)
 {T[u]=t[i]-'A';u+=1;}
 cin>>n;
 br2=u-1;
}

void check2()
{int j,i,m,b=0;
 m=strlen(s);
 for( j=0;j<m;j++)
  for( i=1;i<=n;i++)
   if(s[j]==P[i]+'A')
	{while(j<m)
	 {if(s[j]!=(P[i++]+'A'))break;j++;}
	 if(j==m)b=1;
	}
 if(!b)br++;
}
void perm(int p)
{
 for(int i=1;i<=br2;i++)
 {P[p]=T[i];
  if(p==n){check2();}
   else perm(p+1);
 }
}
int main()
{
vhod();
 perm(1);
 cout<<br<<"\n";
} 
  
