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

Syöte

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

Sitten syötteessä on n lukua, joista kukin sisältää kolme kokonaislukua a, b ja c.

Tuloste

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

Rajat

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

Esimerkki

Syöte:

3
3 7 1
15 2 2
3 4 5

Tuloste:

2187
50625
763327764