JDCC '15 Contest 5 P5 - Domino Tilings

View as PDF

Submit solution

Points: 17
Time limit: 4.0s
Memory limit: 512M

Problem types

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 N rows and M columns.

Remember that dominoes are 1 \times 2 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 N = 3 then the following pattern is forbidden:

Input Specification

The first line of input provides the number of test cases, T (1 \le T \le 100). T test cases follow. Each test case contains two integers N, M (1 \le N \le 6, 1 \le M \le 10^{15}).

For the first 30\% of cases, N \times M \le 40

For the first 70\% of cases, M \le 50

Output Specification

For each test case, your program should the number of ways to tile the rectangle with dominoes, modulo 10^9+7.

Sample Input

1 10
2 10
3 4
3 10
6 20

Sample Output


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:


There are no comments at the moment.