1 /************************************************************** 2     Problem: 1566 3     User: rausen 4     Language: Pascal 5     Result: Accepted 6     Time:11920 ms 7     Memory:3592 kb 8 ****************************************************************/ 9  10 const prime = 1024523;11  12 var13   s1, s2 : array[0..600] of char;14   m, n, i, j, k, j1, k1 : longint;15   p, q : longint;16   f : array[0..1, 0..600, 0..600] of longint;17  18 procedure reverse;19 var20   s : ansistring;21   i : longint;22  23 begin24   readln(s);25   for i := 1 to m do26     s1[m - i + 1] := s[i];27   readln(s);28   for i := 1 to n do29     s2[n - i + 1] := s[i];30 end;31  32 begin33   readln(m, n);34   reverse;35   f[0, 1, 1] := 1;36   for i := 1 to m + n + 1 do begin37     p := i mod 2;38     q := p xor 1;39     fillchar(f[p], sizeof(f[p]), 0);40     for j := 1 to m + 1 do41       for k := 1 to m + 1 do42         while f[q, j, k] >= prime do43           dec(f[q, j, k], prime);44     for j := 1 to m + 1 do45       for k := 1 to m + 1 do begin46         j1 := i - j + 1;47         k1 := i - k + 1;48         if (j1 > 0) and (k1 > 0) and (j1 <= n + 1) and (k1 <= n + 1) then begin49           if s1[j] = s1[k] then inc(f[p, j + 1, k + 1], f[q, j, k]);50           if s1[j] = s2[k1] then inc(f[p, j + 1, k], f[q, j ,k]);51           if s2[j1] = s1[k] then inc(f[p, j, k + 1], f[q, j ,k]);52           if s2[j1] = s2[k1] then inc(f[p, j, k], f[q, j, k]);53         end;54       end;55   end;56   writeln(f[q, m + 1, m + 1]);57 end.