Rohan is a great astronaut and a scientist. He lands in a Strange Planet. After searching the planet for days, he notices something strange. He thinks that this might be the sign of life. He sees that, small creatures keep on increasing in pits. These creatures can form new creatures among themselves. He gets very scared when he notices that the Pits keeps increasing too! He goes back to his spaceship and sits down with a pen and a paper to analyze the data so collected. Rohan gets to know by his mathematical abilities that the number of pits at any hour N is $A^N$, where ‘A’ is the number of creatures in the pit (all pits have the same number of creatures) at the 0th hour.

He finds that it takes $A^N$ creatures to produce a new creature. And the creature does not reproduce with those creatures in their own pit. One creature can only reproduce when all the other creatures are from another pit .

Rohan messaged this fact to his base on Earth. He wants to know the number of ways in which a new creature can be produced. You being his friend and his colleague, have to give him the number of ways in which a new creature can be produced from the existing creatures. As the number can be very large. So print the number modulo $10^9+7$.

Input

First Input Line contains T, the number of test cases.

Second Input line contains two space separated integers A and N .

Output

Print the desired Output modulo $10^9+7$.

Constraints

$1 \le T \le 1000.$

$1 \le A < 100 .$

$1 \le N \le 10^{18} .$