Tehtäväsi on laskea nopeasti joukko laskuja muotoa a^b modulo 10^9+7.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku n: laskujen määrä.

Sitten syötteessä on n riviä, joista kukin sisältää kaksi kokonaislukua a ja b.

Tuloste

Tulosta jokaisen laskun vastaus a^b modulo 10^9+7 omalle rivilleen.

Rajat

• 1 \le n \le 10^5
• 0 \le a,b \le 10^9

Esimerkki

Syöte:

3
3 4
2 8
123 123

Tuloste:

81
256
921450052