Gandalf the Grey

All submissions for this problem are available.
Gandalf has many great magical powers. Sauron is the 'ONLY' enemy of Gandalf. Gandalf gets news from his secret agent that Sauron is going to attack. Before the final attack Sauron will send 'n' warmachines(distinct) in n boxes(1 in each box).Each box will contain manual for the respective machine.Sauron's orcs are unskilled and inexperienced,so they cannot handle these warmachines without correct manuals. Gandalf decides to change the position of manuals from one box to another using his magicpower so that some or all manuals will be placed in wrong boxes.
Lord Elrond tells Gandalf that if they become successful in placing 'm' manuals at wrong places they will win the war.
Let P be the maximum number of ways to do this. Gandalf will try all the ways and then decide one among them.First try takes 1 magical power unit(mpu) ; 2nd try takes 1 mpu ; 3rd try takes 2 mpu and similarly: mpus required for 'i'th try = mpu taken for (i1)th try +mpu taken for (i2)th try
M(i)=M(i1)+M(i2)
Print the magical power units required for last try,for the given value of n and m. As this value will be large,Print the answer mod 100003 (10^5+3).
Input
 The first line of the input contains an integer T denoting the number of test cases.
 The next T lines contain:
 Each test case contains two integers n and m.
Output
 For each test case, output a single line containing the answer mod 100003.
Constraints
 1 ≤ T ≤ 10000
 1 ≤ n < 20
 1 ≤ m ≤ n
Example
Input: 1 4 2 Output: 8
Explanation
Case 1.
For 4 Boxes 1,2,3 and 4 with a,b,c and d as respective manuals; 2 manuals can be placed in wrong boxes in following ways:
1 2 3 4
a b 'd' 'c'
a 'c' 'b' d
'c' b 'a' d
'b' 'a' c d
'd' b c 'a'
a 'd' c 'b'
Thus the sixth try will take 8 magical power units.
Author:  akshaykolte_17 
Tags  akshaykolte_17 
Date Added:  7032015 
Time Limit:  0.2 sec 
Source Limit:  50000 Bytes 
Languages:  CPP 4.3.2, CPP 6.3, CPP14 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 