Strange Creatures
Tag(s):

## Medium

Problem
Editorial
Analytics

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} .$

SAMPLE INPUT
1
2 3
SAMPLE OUTPUT
256
Explanation

For TestCase 1 (T=1).

Number of creatures in each pit=2

Number of pits at the hour 3 = $2^3$ = 8.

So, the number of ways of selecting 8 creatures from 8 pits to reproduce
= $^2P_1* ^2P_1* ^2P_1* ^2P_1* ^2P_1* ^2P_1* ^2P_1* ^2P_1=256$.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

## CODE EDITOR

Initializing Code Editor...