Program Subsir_comun_distincte;
var fi,fo :text;
    a,b:array[0..500] of char;
    i,j,k,l1,l2,m2:integer;
    c,best:array[0..500,0..500] of integer;

Function max(a,b : integer):integer;
begin
    if a>b then max:=a
           else max:=b;
end;

begin
     assign(fi,'subsir.in'); reset(fi);
     assign(fo,'subsir.out'); rewrite(fo);
     l1:=0;
     while not(eoln(fi)) do begin l1:=l1+1; read(fi,a[l1]); end; readln(fi);
     l2:=0;
     while not(eoln(fi)) do begin l2:=l2+1; read(fi,b[l2]); end;
     for i:=0 to l1 do c[i,0]:=1;
     for i:=1 to l2 do c[0,i]:=1;

     for i:=1 to l1 do
       for j:=1 to l2 do
              if a[i-1]=b[j-1] then begin
                                    best[i,j]:=best[i-1,j-1]+1;
                                    c[i,j]:=c[i-1,j-1];
                                    end
                               else if best[i-1,j]=best[i,j-1]
                                           then begin
                                                best[i,j]:=best[i-1,j];
                                                c[i,j]:=(c[i-1,j]+c[i,j-1]) mod 666013;
                                                if best[i-1,j-1]=best[i-1,j] then
                                                             c[i,j]:=(c[i,j]-c[i-1,j-1]+666013) mod 666013;
                                                end
                                            else
                                                if best[i,j-1]>best[i-1,j] then
                                                                begin
                                                                 best[i,j]:=best[i,j-1];
                                                                 c[i,j]:=c[i,j-1];
                                                                 end
                                                             else begin
                                                              best[i,j]:=best[i-1,j];
                                                              c[i,j]:=c[i-1,j];
                                                                  end ;


     write(fo,c[l1,l2]);
     close(fi); close(fo);
end.