{
TASK:string
LANG:Pascal
}
var
  n,i,j,k,p: Integer;
  a: array[0..2000] of Integer;
  s,s1,t: String;
  br: Int64;

procedure scan;
var
  i: Integer;
  fl: Boolean;

begin
  fl:= false;
  for i:= 1 to n do
    if pos(s,s1) = i then
      fl:= true;
  if not fl then
    br:= br+1;
  br:= br mod 1000000;

end;

begin
  readln(s);
  readln(t);
  readln(p);
  n:= length(t);
  for i:= 1 to p do
    a[i]:= 1;

  i:= p;
  k:= 1;
  br:= 0;
  while (a[i] <= n) and (k<>0) do
  begin
    s1:= '';
    for j:= 1 to p do
      s1:= s1 + t[a[j]];
    scan;

    a[i]:= a[i]+1;
    k:= i;
    while (a[k] > n) and (k > 0) do
    begin
      a[k-1]:= a[k-1] + 1;
      for j:= k to p do
        a[j]:= 1;
      k:= k-1;
    end;
  end;
  writeln(br);
end.