나이트

$M$행 $N$열 크기의 체스판에 나이트를 놓는다. 한 칸에는 나이트를 최대 한 개까지 놓을 수 있다.

체스판에 놓인 나이트는 서로 공격할 수 없어야 한다. 나이트는 한 방향으로 두 칸 간 뒤 그 방향과 수직으로 한 칸 간 위치를 공격한다. 아래 그림에서 가운데 나이트가 공격하는 칸을 X로 표시했다.

체스판의 크기가 주어지면 나이트를 놓는 방법의 수를 구하는 프로그램을 작성하시오. 나이트를 하나도 놓지 않는 경우도 한 가지 방법으로 센다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 10$)

이어지는 $T$개의 줄에 테스트 케이스가 하나씩 주어진다. 각 줄에 체스판의 크기를 나타내는 두 정수 $M$과 $N$이 공백을 두고 주어진다. ($1 \le M \le 4$, $1 \le N \le 10^9$)

각 테스트 케이스마다 나이트를 놓는 방법의 수를 1,000,000,009로 나눈 나머지를 한 줄에 출력한다.