Algorytm2

type mas=array[0..1000,0..1000] of longint;
     vector=array[0..1000,0..1000] of char;
var a:vector; b:mas;
    ii,jj,i,j,n,k,f,l:longint;s:string;x,c,c1:char;

function max(aa,bb:longint):longint;
begin
   if aa>bb then max:=aa else max:=bb;
end;

begin
 readln (n);     k:=0;  c:='f';
 for i := 1 to n do
  begin

    for j := 1 to n do  begin read(x);a[i,j]:=x;if x=c then k:=k+1;c:=x;
                        end; readln;
   end;

   readln(s);

  if n*n-1=k then
   begin
   f:=1;
     for I := 1 to n do
       f:=(f*i) mod 1000003;
       writeln(f)
   end   else
   begin

    c:=s[1];
    c1:=s[2*n-1];
 if (a[1,1]<>c)or (a[n,n]<>c1) then  writeln(0) ELSE
begin
   b[1,1]:=1;
   for I := 2 to n do
     begin
     if (a[1,i]=s[i]) and (b[1,i-1]<>0) then  b[1,i]:=1;
     if (a[i,1]=s[i]) and (b[i-1,1]<>0) then  b[i,1]:=1;
    end;

     for I := 2 to n do
     for j := 2 to n do
       begin
         if a[i,j]=s[i+j-1] then
          begin
          if (a[i-1,j]<>a[i,j-1]) then b[i,j]:=max(b[i-1,j],b[i,j-1])  else
          b[i,j]:=(b[i,j-1] mod 1000003+b[i-1,j] mod 1000003) mod 1000003;
          end ;

       end;


    writeln(b[n,n] mod 1000003);
    end;      end;

end.