Gap Filler Game

Problem code: GAPFILL

All submissions for this problem are available.

Now we are all bored playing, probably that is why they call it board game.

Chef is facing severe problems at his restaurant. Because his kitchen is small so only small number of cooks can fit in which results in slow service. Customers don't like waiting for their food. While he has already started looking for new place to move in, this might take some time. So in meanwhile he has come up with an innovative idea. He'd put up a board game puzzle on all tables so that customers can play the game while waiting for their orders to arrive. To make this gap filler idea more viral, he'd further give a discount to people who successfully solve the puzzle.

Game that he has chosen consists of N * M grid with each cell having a light and a switch. Once a switch of a cell is pressed, all lights in the same column or row including the cell toggle once. Note that light in the cell whose switch is pressed is toggled once and not twice. Game starts with some lights on and rest off and the objective of the game is to turn on all the lights.

He however fears that a lot of people may win discounts. He is a great cook but he is not good with puzzle solving. He seeks your help in determining how easy or tough this game is. Given board dimensions, your task is to find out how many initial configurations of the game can be solved. Two configurations are different if there is at least one cell which is off in one and on in other. As this number might get huge, only print the answer modulo 10^9 + 7.

Input

First line of the input contains a single integer T, the number of test cases. Each of the next T lines represents a single test case containing two integers N & M separated by a space. N & M are the dimensions of the board. You can assume that T <= 50000 and 1 <= N,M <= 10^18

Output

For each test case, print the number of initial configurations of N * M board that can be solved modulo 10^9 + 7.

Example

Input:
3
1 1
1 3
3 3

Output:
2
2
32

Description :
In first case 1 * 1 board can have 2 configurations - off or on. Both can be solved.
In second case we've a row of 3 lights. There are total of 8 configurations. Out of these only 2 configurations can be solved (one with all lights on and one with all lights off)

Author: yellow_agony
Date Added: 20-11-2011
Time Limit: 1 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

when the switch of a cell is

praveen97uma @ 1 Jan 2012 08:52 PM
when the switch of a cell is pressed, either only a row or column toggle or both can toggle simultaneously?

@praveen97uma : Its mentioned

nikhil_adm @ 1 Jan 2012 10:52 PM
@praveen97uma : Its mentioned clearly in the problem statement that when a switch is pressed, all lights in the same row or column as that of pressed switched toggle their state. So lights sharing the row toggle as well as lights sharing the column toggle.

can someone explain 3rd case

h_25 @ 2 Jan 2012 12:09 AM
can someone explain 3rd case

@h_25 Please think about the

hiroto_adm @ 2 Jan 2012 02:37 AM
@h_25 Please think about the 3rd example by yourself. If you think the problem statement has ambiguities, please indicate them.

@praveen: I think the problem

ishandutta2007 @ 4 Jan 2012 10:48 PM
@praveen: I think the problem setter means "all lights in the same row AND same column toggle" by saying "all lights in the same column OR row toggle"

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions