URI Online Judge | 2100

Xing Tzen Zu’s Movie Theater

By XIII Maratona de Programação IME-USP, 2009 BR Brazil

Timelimit: 1

Harbin has one of the biggest movie theaters in the world. The "Xing Tzen Zu" movie theater is very wide, with few rows and many chairs. The chinese goverment has specific rules for people to go to the movies: each couple must sit on the same row (the first row is occupied by farmers, drivers, mechanics, the second by teachers, salesmen, firemen, and so on). But, at the same time, it is forbidden for people to sit on the same position in two nights. That worried the mayor, who then tried to find how many nights the movie theater could open without the need to repeat a layout that had occurred before. An important restriction is that couples must always occupy neighboring seats on the row.

Your task on this problem is to determine, given the number of seats N and the number of couples M, how many different ways the couples can seat on the chairs in a way they are not separated.


The input is composed by several instances. The first line of the input has an integer number T indicating the number of instances. Each instance is composed by a line that has two integer numbers N (2 ≤ N ≤ 4000) and M (1 ≤ MN/2).


For each instance print a line that has the number of different ways the couples could sit on the chairs in a way they are not separated.

The answer must be in MOD1300031.

Sample Input Sample Output


10 2

20 6