Knights

You place knights on a chessboard with $M$ rows and $N$ columns. Each square holds at most one knight.

No two knights on the board may attack each other. A knight attacks the square reached by moving two squares in one direction and then one square perpendicular to that direction. In the picture below, the squares attacked by the knight in the center are marked with X.

Given the size of the board, write a program that counts the ways to place the knights. Placing no knight at all counts as one way.

The first line contains the number of test cases $T$. ($1 \le T \le 10$)

Each of the next $T$ lines contains one test case: two integers $M$ and $N$, separated by a space, giving the size of the board. ($1 \le M \le 4$, $1 \le N \le 10^9$)

For each test case, print the number of ways to place the knights modulo 1,000,000,009 on its own line.