Ross works as a palaeontologist at the local museum. He has often tried to convince his friend Phoebe about the science of evolution, but Phoebe just doesn't see how evolution can be true.

To prove his point, Ross has decided to show Phoebe some of the fossils the museum owns, and describe how so many years ago such animals existed.

However, there is one problem. The age of the fossils have been encoded as (x, y) in the museum records where the actual age of the fossil is x^y. This has been done as age of the fossil may be very huge. But Ross has to show some number to Phoebe, so he decides to compute x^y % 1000000007 as a value and show it to Phoebe. As the number of fossils are too great, help him determine the actual value.

Input

First line contains number of test cases T. The first line of each testcase contains two positive integers X and Y.

Output

Output a single positive number with value X^Y % 1000000007.

Constraints

0 < T <= 100000

0 < X, Y <= 10000000