NAC-SAC Game! (Hard. Well, Not Really. 😛)

Remember the game played by Akash and Guru on the NAC-SAC bridge?

(For those cannot remember, Akash and Guru used to play an interesting game on the NAC-SAC bridge. They used to be at the two ends of the bridge. Each of them had number 1 written in on a piece of paper initially and whenever someone crossed the bridge from SAC-NAC, Akash multiplied his current number by 2. Similarly, whenever someone crossed the bridge from NAC-SAC, Guru multiplied his current number by 3. At last when they got tired, they used to meet in the Plaza Area and added up their individual numbers and calculated the remainder when the added number is divided by 1000000007.)

It turned out that standing in front of the bridge all day and multiplying numbers is a tiresome job. So they did not play that game after some days as it was too tiring.

JavaBaba, who is a senior programmer of the community, knew about the game played by them. He gave them an interesting problem to solve. If they kept playing the game and kept multiplying numbers throughout the semester, what would be the outcome?

More specifically, if Akash and Guru kept track of all the people who crossed the bridge throughout the semester and Akash kept multiplying his current number by 2 whenever someone crossed from SAC to NAC and similarly, Guru kept multiplying his current number by 3 whenever someone crossed NAC to SAC and finally at the end of the semester if they added up their respective numbers together, what would be the remainder if the added number is divided by 1000000007?

JavaBaba promised that if they can solve the problem he will give them a grand treat. As treats from JavaBaba are very rare to come, Akash and Guru want to solve this problem at any cost.

As they did not take all the data themselves, they collected security footage from the authority and counted the total number of times people crossed the bridge from SAC to NAC and also the total number of times people crossed the bridge from NAC to SAC. As they are calculating for the whole semester, these numbers can be huge. Please help them to write a program that will calculate the desired result. They have promised you a kacchi treat if you can write this program. And you can do anything for kachhi!

Input

The first line contains a positive integer T (1 ≤ T ≤ 1000) which is the number of test cases. Then T cases follow, each having a single line consisting of two integers X (0 ≤ X ≤ 10^9) and Y (0 ≤ Y ≤ 10^9). Where X is the number of times people have crossed the bridge from SAC to NAC in the whole semester and Y is the number of times people have crossed the bridge from NAC to SAC in the whole semester.

Output

For each test case, output a single integer which is the remainder when the added value got by Akash and Guru is divided by 1000000007.

Sample

Input	Output
4 2 0 2 2 11 27 1000000000 1000000000	5 13 597433660 376564646
In the first case, Akash has got 4 and Guru has got 1. After adding them up, they get 5. After dividing it by 1000000007 they finally get 5.