好题，这道题体现了换一个角度计数的思想
a1^2+a2^2+……ak^2=(变成第1种输出序列的操作序列数目)^2+(变成第2种输出序列的操作序列数目)^2……
脑洞大一点，这就相当于两个操作序列变成相同输出序列的对数（包括自己和自己）
于是dp即可……dp[i,j,k]表示输出到第i个，第一个操作序列在上面取了j个，第二个操作序列在上面取了k个，怎么弄大家都会……
const mo=; var s1,s2:array[..] of char;
p,m,n,i,j,k,j1,k1:longint;
f:array[..,..,..] of longint; procedure reverse;
var s:ansistring;
begin
readln(s);
for i:= to n do
s1[n-i+]:=s[i];
s1[n+]:='$';
readln(s);
for i:= to m do
s2[m-i+]:=s[i];
s2[m+]:='#';
end; begin
readln(n,m);
reverse;
f[,,]:=;
for i:= to m+n do
begin
p:=-p;
fillchar(f[p],sizeof(f[p]),);
for j:= to n do
for k:= to n do
if f[-p,j,k]>=mo then f[-p,j,k]:=f[-p,j,k] mod mo;
for j:= to n do
for k:= to n do
begin
j1:=i--j;
k1:=i--k;
if (j1>=) and (k1>=) and (j1<=m) and (k1<=m) then
begin
if s1[j+]=s1[k+] then inc(f[p,j+,k+],f[-p,j,k]);
if s1[j+]=s2[k1+] then inc(f[p,j+,k],f[-p,j,k]);
if s2[j1+]=s1[k+] then inc(f[p,j,k+],f[-p,j,k]);
if s2[j1+]=s2[k1+] then inc(f[p,j,k],f[-p,j,k]);
end;
end;
end;
writeln(f[p,n,n] mod mo);
end.
