Time Limit:3000ms Memory Limit:65536KB
Description
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.
Input
The first line of the input is an integer T which indicates the number of test cases.
  Each of the following T lines are two integers N (1 í▄ N í▄ 100) and M (1 í▄ M í▄ 10) indicating
  the size of Peterí»s room.

Output
  For each test case, print a line contains the answer.
Sample Input
3
1 1
2 2
4 5
Sample Output
10
626
822267