Program p2;
const rest=666013;
var fi,fo:text; i,j,n,m:longint;
    a,nr:array[0..505,0..505] of longint;
    s1,s2:ansistring;

begin
    assign(fi,'subsir.in'); reset(fi); readln(fi,s1); read(fi,s2);
    assign(fo,'subsir.out'); rewrite(fo); n:=length(s1); m:=length(s2);

    for i:=0 to n+1 do begin a[i,0]:=0; nr[i,0]:=1; end;
    for j:=0 to m+1 do begin a[0,j]:=0; nr[0,j]:=1; end;

    for i:=1 to n do
       for j:=1 to m do
           if s1[i]=s2[j] then begin a[i,j]:=a[i-1,j-1]+1; nr[i,j]:=nr[i-1,j-1]; end
                          else begin
                           if a[i,j-1]>a[i-1,j] then begin a[i,j]:=a[i,j-1]; nr[i,j]:=nr[i,j-1]; end
                                                else if a[i-1,j]>a[i,j-1] then begin a[i,j]:=a[i-1,j]; nr[i,j]:=nr[i-1,j]; end
                                                                              else begin
                                                                                   a[i,j]:=a[i-1,j];
                                                                                   nr[i,j]:=(nr[i-1,j]+nr[i,j-1]) mod rest;
                                                                                   if a[i-1,j-1]=a[i-1,j] then nr[i,j]:=(rest+nr[i,j]-nr[i-1,j-1]) mod rest;
                                                                                   end;
                               end;
    write(fo,nr[n,m]);
    close(fi); close(fo);
end.