{
TASK:string
LANG:Pascal
}
var s,t,rs:string[21];
    i,len,p,br:integer;

procedure gen;
var i:integer;
begin
if (length(rs)=p) {and (pos(s,rs)=0)}
   then inc(br)
   else
     for i:=1 to len do begin
         rs:=rs+t[i];
         if pos(s,rs)=0 then gen;
         delete(rs,length(rs),1);
     end;

end;

begin
     rs:='';  br:=0;
     readln(s);
     readln(t);
     readln(p);
     len:=length(t);
     gen;
     writeln(br);
end.