{
TASK:string
LANG:Pascal
}
program STR;

var
 S: string;
 T: string[52];
 P: word;
 ct: longint;

procedure IncCt;
begin
 if ct=999999 then
  ct:=0
 else
  ct:=ct+1;
end;

procedure GetCt(x: integer; ss: string);
var
 i: byte;
 news: string;
begin
 for i:=1 to length(T) do
 begin
  news:=ss+T[i];
  if x=P then
   if pos(S,news)=0 then
    IncCt;
  if x<P then
   GetCt(x+1,news);
 end;
end;

begin
 readln(S);
 readln(T);
 readln(P);
 ct:=0;
 GetCt(1,'');
 writeln(ct);
end.