On the 6th test(((
why???const
  c=1000000000;
var
  n,m:longint;
  i,j:longint;
  d:longint;
  boo:boolean;
  answer:array[2..5,2..10000000] of byte;
begin
read(n,m);
if (n mod 2 =1) and (m mod 2 =1) then
  begin
   answer[n,m]:=0;
   boo:=true;
  end;
 if n>m then
     begin
      d:=n;
      n:=m;
      m:=d;
     end;
 if n=2 then
        answer[n,m]:=2
        else
           if ((n=3)  and (m mod 2=1)) then
                                         begin
                                          answer[n,m]:=0;
                                         end
                                      else
                                        if ((n=3)  and (m mod 2=0)) then
                                            begin
                                              answer[n,m]:=4;
                                            end



      else
        if (n>3) and (boo<> true)then
           begin
            for i:=2 to m do
             begin
               answer[2,i]:=2;
             end;
              for i:=2 to n do
               begin
                 answer[i,2]:=2;
               end;
              for i:=3 to n do
                for j:=3 to m do
                begin
                  if (i mod 2 =1) and (j mod 2=1) then
                        begin
                         answer[i,j]:=0
                        end
                                                  else
                        begin
                        answer[i,j]:=2*(answer[i-1,j]+answer[i,j-1]);
                         if i=j then
                         begin
                          answer[i,j]:=answer[i,j]-answer[i,j-1];
                         end
                       end;
                end;
           end;
 write(answer[n,m]);
end.

Edited by author 12.08.2006 19:01

2 ≤ M < 10^9.

Your M is up to 10^7.

By the way,
"You should output the number of ways to travel through the board calculated modulo 10^9."

Edited by author 13.08.2006 13:07