Your task is to efficiently calculate values ~a^{b^c}~ modulo ~10^9+7~.

Note that in this task we assume that ~0^0=1~.

Input

• The first input line has an integer ~n~: the number of calculations.

After this, there are ~n~ lines, each containing three integers ~a~, ~b~ and ~c~.

Output

• Print each value ~a^{b^c}~ modulo ~10^9+7~.

Constraints

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

Example Input

3
3 7 1
15 2 2
3 4 5

Example Output

2187
50625
763327764