Problem:

Baba has captured Avni to take revenge from Bajirao. Bajirao fights all of Baba's men and reaches the place where Baba is waiting for Bajirao along with Avni, Avni tied by a rope.

Baba has tied Avni with a magical rope, which will untie itself only when Bajirao answers the question Baba asks him.

Baba asks him T questions. In every question, Baba gives two values to Bajirao, N and k. Bajirao has to calculate the value of

Fact(Fact(Fact(......Fact(N)....))) k times.

where Fact(N) = 1 * 2 * 3 *..... * (N-1) * N.

For example if k=2, Bajirao has to calculate the value of Fact(Fact(N)) and if k=3, Bajirao has to calculate the value of Fact(Fact(Fact(N))).

Since this number can be really huge, Baba asks Bajirao to give his answer modulo 107 ie. Bajirao has to give the remainder when Fact(Fact(Fact(......Fact(N)....))) k times is divided by 107.

Input :

First line consists of T, the number of questions Baba is going to ask Bajirao. After that, T lines follow, each line consisits of 2 space separated integers, N followed by k.

Output:

For every question asked by Baba, print the correct answer on a new line.

Constraints :

1<=T<=100

1<=N<=1000000

2<=k<=100

Problem Setter : Shreyans

Problem Testers : Sandeep , Himanshu

(By IIT Kgp HackerEarth Programming Club)