{
TASK:string
LANG:Pascal
}

program string01;
var p,l,i,j:integer;
    t,s:string;
    a,b,c,y:longint;

begin
 readln(s);
 readln(t);
 readln(p);
 l:=length(s);
 a:=1;
 b:=1;
 for i:=1 to p do
 begin
  a:=a*length(t);
  a:=a mod 1000000;
 end;
 b:=0;
 for i:=(p-l+1) downto 1 do
 begin
  y:=1;
  for j:=(i-1) downto 1 do
  begin
   y:=y*length(t);
   y:=y mod 1000000;
  end;
  b:=b+y;
 end;
 if a<b then c:=a-b+1000000
 else c:=a-b;
 writeln(c);
end.