Peter took part in ACM school tour of South China University of Technology and gained munificent
rewards. The first thing he would like to do after he gets the money is to pave the beautiful
floorboards for his bedroom. The floor of Peterí»s bedroom is an N*M rectangular. In the store,
there are four types of 1*1 ceramic tiles.
Each ceramic tile has many stocks, which could be considered as limitlessness. Peter thinks that
the plan is splendid, if the neighboring sides of adjacent unit tiles have the same color.
Now Peter would like to know that how many plans there are that he could pave beautiful floorboards
for his bedroom. You're allowed to rotate unit tiles arbitrarily, however, the corner of the floor
is fixed (i.e., the colorings that are rotations of each other are considered different). Because the
figure may be quite large, Peter only wants to know the answer mod 1,000,003.