program bla;
var f,g:text;
    d,e:array[0..500,0..500] of longint;
    n,m,i,j:byte;
    a,b:ansistring;

function max (a,b:longint):longint;
begin
 if a> b then max:=a
 else max:=b;
end;

begin
 assign (f,'subsir.in'); reset(F);
 assign (g,'subsir.out'); rewrite (g);
 readln (f,a);
 readln (f,b);
 n:=length(a); m:=length(b);
 for i:=1 to m do
  e[0,i]:=1;
 for i:=1 to n do
 begin
  e[i,0]:=1;
  for j:=1 to m do
   if a[i]=b[j] then
    d[i,j]:=d[i-1,j-1]+1
   else
    d[i,j]:=max(d[i-1,j], d[i,j-1]);
    if a[i]=b[j] then
     e[i,j]:=e[i-1,j-1]
    else
    begin
     e[i,j]:=0;
     if d[i,j]=d[i-1,j] then
      e[i,j]:=(e[i,j]+e[i-1,j]) mod 666013;
    end;
    if d[i,j]=d[i,j-1] then
     e[i,j]:=(e[i,j]+e[i,j-1]) mod 666013;
    if d[i,j]=d[i-1,j-1] then
     e[i,j]:=(e[i,j]-e[i-1,j-1]+666013) mod 666013;
 end;
 write (g,e[n,m]);
 close (F); close (G);
end.