var v,m,p:array[0..500,0..500]of longint;
    a,b:array[0..500]of char;
    u1,u2:array[0..500,1..26]of longint;
    n,i,j,k,l1,l2,l,x,y,s:longint;
    c:char;
    f:text;
begin
   assign(f,'subsir.in');
   reset(f);
   while not eoln(f)do
   begin
   read(f,c);
   if c in ['a'..'z'] then begin l1:=l1+1;
                                 a[l1]:=c;
                           end;
   end;
   readln(f);
   while not eoln(f)do
   begin
   read(f,c);
   if c in ['a'..'z'] then begin l2:=l2+1;
                                 b[l2]:=c;
                           end;
   end;
   readln(f);
   close(f);
   for i:=1 to l1 do
   for j:=1 to 26 do
   if ord(a[i])-96=j then u1[i,j]:=i
                     else u1[i,j]:=u1[i-1,j];
   for i:=1 to l2 do
   for j:=1 to 26 do
   if ord(b[i])-96=j then u2[i,j]:=i
                     else u2[i,j]:=u2[i-1,j];
   for i:=1 to l1 do
   for j:=1 to l2 do
   begin
   if a[i]=b[j] then v[i,j]:=m[i-1,j-1]+1;
   if v[i,j]>m[i,j] then m[i,j]:=v[i,j];
   if m[i-1,j]>m[i,j] then m[i,j]:=m[i-1,j];
   if m[i,j-1]>m[i,j] then m[i,j]:=m[i,j-1];
   if v[i,j]<=1 then p[i,j]:=v[i,j]
                else begin for l:=1 to 26 do
                           begin
                           x:=u1[i-1,l];
                           y:=u2[j-1,l];
                           if v[x,y]+1=v[i,j] then p[i,j]:=(p[i,j]+p[x,y])mod 666013;
                           end;
                     end;
   end;
   assign(f,'subsir.out');
   rewrite(f);
   for i:=1 to l1 do
   for j:=1 to l2 do
   if(u1[l1,ord(a[i])-96]=i)and(u2[l2,ord(b[j])-96]=j)and(v[i,j]=m[l1,l2])then s:=(s+p[i,j])mod 666013;
   writeln(f,s);
   close(f);
end.