David's favourite activity in the world is playing with dominoes. David especially loves to arrange the dominoes into neat rectangles. Luckily for him, he has found that there are many different ways to tile a rectangle. He wonders in how many different ways can he tile a rectangle with rows and columns.
Remember that dominoes are blocks that can be arranged horizontally or vertically. To make his life easier, he won't be counting any tilings that contain a complete column of horizontal tiles. For example, if then the following pattern is forbidden:
Input Specification
The first line of input provides the number of test cases, . test cases follow. Each test case contains two integers .
For the first of cases,
For the first of cases,
Output Specification
For each test case, your program should the number of ways to tile the rectangle with dominoes, modulo .
Sample Input
1
1 10
2 10
3 4
3 10
6 20
Sample Output
0
1
6
162
461383751
Explanation for Sample
In the first test case, placing a horizontal block would count as a complete column of horizontal tiles, which means that there are no valid tilings.
In the second test case, the only valid tiling is one of vertical blocks, since placing a horizontal block would force you to place another one in the same column.
In the third test case, here is an example tiling:
Comments