const pp=666013;
{var a,b,aux,x:string;k,max,i,j,l,h,y,z:integer;f,g:text;
c:array[1..100]of string;d,e:array[1..250]of char;}
var f,g:text;a,b:array[1..500]of char;c,d:array[1..100]of string;
n,m,i,j,k,max,x,y,l,q,o,w,u:integer;r,p:string;
begin
assign(f,'subsir.in');reset(f);
assign(g,'subsir.out');rewrite(g);
while not eoln(f) do begin n:=n+1;read(f,a[n]);end;readln(f);
while not eoln(f) do begin m:=m+1;read(f,b[m]);end; max:=0;k:=0;r:='';p:='';
{max:=0;h:=0;l:=0;
if length(a)>length(b) then begin aux:=a;a:=b;b:=aux;end;
for i:=1 to length(a) do begin    k:=0;x:='';
for j:=i to length(a) do begin
x:=x+a[j];
if pos(x,b)>0 then begin k:=k+1;if k>max then max:=k;end
              else begin k:=0;break;end;
end;end;
for i:=1 to length(a) do begin    k:=0;x:='';
for j:=i to length(a) do begin
x:=x+a[j];
if pos(x,b)>0 then begin k:=k+1;if k=max then begin h:=h+1;c[h]:=x;k:=0;end;end
              else begin k:=0;break;end;
end;end;
for i:=1 to h-1 do
for j:=i+1 to h do
if c[i]>c[j] then begin aux:=c[i];c[i]:=c[j];c[j]:=aux;end;
for i:=1 to h do
if c[i]<>c[i+1] then l:=l+1;
write(g,l mod p);}
for i:=1 to n do
for j:=1 to m do
if a[i]=b[j] then begin
x:=i;y:=j;
while (a[x]=b[y])and(x<=n)and(y<=m) do begin
k:=k+1;x:=x+1;y:=y+1;end;
if k>max then max:=k;k:=0;end;
k:=0;
for i:=1 to n do
for j:=1 to m do
if a[i]=b[j] then begin k:=0;
x:=i;y:=j;
while (a[x]=b[y])and(x<=n)and(y<=m) do begin
k:=k+1;x:=x+1;y:=y+1;end;
if k=max then begin
for q:=j to (j+max-1+j)diV 2 do r:=r+b[q];
for q:=(j+max-1+j)diV 2+1 to j+max-1 do p:=p+b[q];
o:=o+1;c[o]:=r;d[o]:=p;
r:='';p:='';end; end;
for i:=1 to o do begin w:=0;
for j:=i+1 to o do
if (c[i]=c[j])and(d[i]=d[j]) then begin w:=1;break;end;
if w=0 then u:=u+1;end;
write(g,u mod pp);
close(g);
end.