For this Question: Modulo exponentiation is super awesome. But can you still think of a solution to the following problem?
Given three integers {a, b, c}, find the value of a<sup>b<sup>c</sup></sup> % 1000000007.
Here a<sup>b</sup> means a raised to the power b or pow(a, b). Expression evaluates to pow(a, pow(b, c)) % 1000000007.

(Read Euler's Theorem before solving this problem)The first input line has an integer t: the number of test cases.
After this, there are n lines, each containing three integers a, b and c.


Constraints
1≤  t ≤ 100
0 ≤  a, b, c ≤ 1000000000For each test case, output the value corresponding to the expression.Sample Input
3
3 7 1
15 2 2
3 4 5

Sample Output
2187
50625
763327764

Explaination:
In the first test, a = 3, b = 7, c = 1
b<sup>c</sup> = 7<sup>1</sup> = 7
a<sup>b<sup>c</sup></sup> = 3<sup>7</sup> = 2187, I have written this Solution Code: import java.io.*;
import java.util.*;



class Main {
    public static void main (String[] args)throws IOException{

        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int T=Integer.parseInt(br.readLine());
        for(int k=0;k<T;k++)
        {
            String[] str= br.readLine().split(" ");
            int a=Integer.parseInt(str[0]);
            int b=Integer.parseInt(str[1]);
            int c=Integer.parseInt(str[2]);
            int M=1000000007;
            System.out.print(superExponentation(a,superExponentation(b,c,M-1),M));
            System.out.println();
        }
    }
    public static long superExponentation(long a,long b,int m)
        {
            long res=1;
            while(b>0)
            {
                if(b%2!=0)
                res=(long)(res%m*a%m)%m;
                a=((a%m)*(a%m))%m;
                b=b>>1;
            }
            return res;
        }
}, In this Programming Language: Java, Now tell me if this Code is compilable or not?