program subsir;

const ct=666013;

var s,d:string;//ansistring;
    w:array[0..500,0..500]of int64;
    nr:int64;

procedure citire;
begin
assign(input,'subsir.in');
reset(input);
readln(s);
readln(d);
close(input);
end;

procedure rezolvare;
var max:int64;
    i,j:integer;
begin
max:=0;
nr:=0;
for i:=1 to length(s) do
    for j:=1 to length(d) do
        begin
        if s[i]=d[j] then
           begin
           if (i=1) or (j=1) then
              w[i,j]:=1
              else w[i,j]:=w[i-1,j-1]+1;
           if w[i,j]=1 then
              inc(w[i,0]);
           end;
        if w[i,j]>max then
           begin
           max:=w[i,j];
           nr:=0;
           end
           else if (w[i,j]=max) and (i>=max) and (w[i-max+1,0]=1) then
                   inc(nr);
        nr:=nr mod ct;
        end;
end;

begin
citire;
nr:=0;
rezolvare;
assign(output,'subsir.out');
rewrite(output);
write(nr mod ct);
close(output);
end.