Задача 4C. Возведение в (возведение в степень) ≡

Условие

Вам необходимо по заданным трем неотрицательным целым числам $a$, $b$ и $c$ эффективно отвечать на вопрос: чему равен остаток от деления $a^{b^c}$ на $10^9 + 7$?

Обратите внимание, что степени считаются справа налево, то есть $a^{b^c} =a^{(b^c)}$.

Формат входных данных

Первая строка входных данных содержит единственное целое число $n$: количество запросов.

В каждой из следующих $n$ строк содержатся три целых числа $a$, $b$, $c$.

Формат выходных данных

Для каждого запроса выведите значение $a^{b^c}$ по модулю $10^9 + 7$.

Ограничения

$1 \le n \le 10^5$

$0 \le a,\,b,\,c \le 10^9$

Примеры тестов

3
3 7 1
15 2 2
3 4 5

2187
50625
763327764