Great Power

Let g(a,b) = a^b mod (10^9 + 7) and f(a,b,c,d) = g(a,b)^c^d mod (10^9 + 7) Input The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. Each test case contains four space-separated integers a, b, c, d Output For each test case output a single integer f(a,b,c,d) Constraints - 1 ≤ T ≤ 105 - 1 ≤ a, b, c, d ≤ 109 Example