Nam is playing with tiles of size 1 x 2. He is trying to put his tiles into a rectangle board of size M x N. He put tiles according to following rules:

1. Tiles can be put horizontally or vertically, and should be inside the board.
2. No two tiles should overlap.
3. It is not necessary to cover the whole rectangle.

Nam wonders, how many final configurations he can get? Since the size of the board is too big, he can't determine the answer. Can you help him?

Input

The first line is T — the number of test cases.

Each of T following lines consists of 2 positive integers M and N — height and width of the rectangular board.

Output

Output should consist of T lines, each line is a number of final configurations. Since the answer can be large, you should print it modulo 1000000007(10⁹ + 7).

Constraints

• 1 ≤ T ≤ 10;
• 1 ≤ M ≤ 6;
• 1 ≤ N ≤ 10⁶
• 10% number of tests in which 1 ≤M, N ≤ 3
• 10% number of tests in which M = 1
• 10% number of tests in which M = 2
• 20% number of tests in which 1 ≤ N ≤ 10000