{
TASK:string
LANG:Pascal
}
program astring;

var Answer: LongInt;
    S: AnsiString;
    T: String;
    P: Integer;

procedure Input;
var Temp: String;
    iChar: Integer;
begin
 ReadLn(S);
 ReadLn(T);
 ReadLn(P);
end;

function Valid(const CheckSTR: AnsiString): Boolean;
var Res: Boolean;
    iChar, Lng: Integer;
begin
 Valid := True;

 Lng := Length(CheckSTR);
 If (Lng < Length(S)) then Exit;

 for iChar := 0 to Length(S) - 1 do begin
  If not(CheckSTR[Lng - iChar] = S[Length(S) - iChar]) then Exit;

 end;

 Valid := False;
end;

procedure DFS(const Lng: Integer; const P_S: AnsiString);
var NewPS: AnsiString;
    iChar: Integer;
begin
 If (Lng = P) then Inc(Answer)
 else begin

  for iChar := 1 to Length(T) do begin
   NewPS := P_S + T[iChar];
   If (Valid(NewPS)) then DFS(Lng + 1,NewPS);
  end;

 end;
end;

begin
 Answer := 0;

 Input;

 DFS(0,'');

 WriteLn(Answer mod 1000000);
end.