Program lg;
var a,b : array[0..501] of 'a'..'z';
    n,m,p,md,z : longint;
    dra,drb : array[0..501,'a'..'z'] of longint;
    r,s : array[0..501,0..501] of longint;
    fout : text;
Procedure citire;
var fin : text;
    i : integer;
begin
assign(fin,'subsir.in');
reset(fin);
n:=1;
m:=1;
while not eoln(fin) do
begin
read(fin,a[n]);
inc(n);
end;
readln(fin);
while not eoln(fin) do
begin
read(fin,b[m]);
inc(m);
end;
dec(n);
dec(m);
end;

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

Procedure preprocesare;
var i,j : integer;
begin

 for i:=1 to n do
   begin
   dra[i]:=dra[i-1];
   dra[i,a[i]]:=i;
   end;
 for i:=1 to m do
 begin
 drb[i]:=drb[i-1];
 drb[i,b[i]]:=i;
 end;
end;

Procedure find;
var i,j : integer;
    c : char;
begin
z:=-MaxInt;
for i:=1 to n do
   for j:=1 to m do
   if a[i]=b[j] then
   begin
   s[i,j]:=s[i-1,j-1]+1;
   if z<s[i,j] then z:=s[i,j];
   for c:='a' to 'z' do
   if s[i,j]=s[dra[i-1,c],drb[j-1,c]]+1 then r[i,j]:=(r[i,j]+r[dra[i-1,c],drb[j-1,c]]) mod md;
   if r[i,j]=0 then r[i,j]:=1;
   end
   else
   s[i,j]:=max(s[i-1,j],s[i,j-1]);
   for c:='a' to 'z' do
   begin
   if s[dra[n,c],drb[m,c]]=z then
   p:=(p+r[dra[n,c],drb[m,c]]) mod md;
   end;
end;



begin
md:=666013;
citire;
preprocesare;
find;
assign(fout,'subsir.out');
rewrite(fout);
writeln(fout,p);
close(fout);
end.