const maxn=501;
type sir = string;
var f:text;
a,b:sir;
c:array[0..maxn,0..maxn]of integer;
d:array[0..maxn,0..maxn]of sir;
sol:array[1..1000000]of sir;
ok:boolean;
n,m,i,j,max,nr,k:longint;
procedure readdata;
begin
assign(f,'subsir.in');
reset(f);
i:=0;
while not eoln(f) do
begin
inc(i);
read(f,a[i]);
end;
m:=i;
readln(f);
i:=0;
while not eoln(f) do
begin
inc(i);
read(f,b[i]);
end;
n:=i;
close(f);
end;
procedure solve;
begin
for i:=1 to m do
begin
c[i,0]:=0;
end;
for i:=1 to n do
begin
c[0,i]:=0;
end;
max:=0;
for i:=1 to m do
begin
for j:=1 to n do
begin
if a[i]=b[j] then
begin
c[i,j]:=c[i-1,j-1]+1;
d[i,j]:=d[i-1,j-1];
d[i,j,c[i,j]]:=a[i];
if c[i,j]>max then
begin
max:=c[i,j];
nr:=0;
end;
if c[i,j]=max then
begin
ok:=false;
for k:=1 to nr do
begin
if sol[k]=d[i,j] then
begin
ok:=true;
end;
end;
if ok=false then
begin
inc(nr);
sol[nr]:=d[i,j];
end;
end;
end
else
begin
if c[i-1,j]>=c[i,j-1] then
begin
c[i,j]:=c[i-1,j];
d[i,j]:=d[i-1,j];
end
else
begin
c[i,j]:=c[i,j-1];
d[i,j]:=d[i,j-1];
end;
end;
end;
end;
for i:=1 to m do
begin
for j:=1 to n do
begin
if a[i]=b[j] then
begin
c[i,j]:=c[i-1,j-1]+1;
d[i,j]:=d[i-1,j-1];
d[i,j,c[i,j]]:=a[i];
if c[i,j]>max then
begin
max:=c[i,j];
nr:=0;
end;
if c[i,j]=max then
begin
ok:=false;
for k:=1 to nr do
begin
if sol[k]=d[i,j] then
begin
ok:=true;
end;
end;
if ok=false then
begin
inc(nr);
sol[nr]:=d[i,j];
end;
end;
end
else
begin
if c[i-1,j]>c[i,j-1] then
begin
c[i,j]:=c[i-1,j];
d[i,j]:=d[i-1,j];
end
else
begin
c[i,j]:=c[i,j-1];
d[i,j]:=d[i,j-1];
end;
end;
end;
end;
end;
procedure writedata;
begin
assign(f,'subsir.out');
rewrite(f);
writeln(f,nr mod 666013);
close(f);
end;
begin
readdata;
solve;
writedata;
end.