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

Автор:CSES   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

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

Обратите внимание, что степени считаются справа налево, то есть abc = a(bc).

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

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

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

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

Для каждого запроса выведите значение abc по модулю 109 + 7.

Ограничения

1 ≤ n ≤ 105

0 ≤ a, b, c ≤ 109

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

Стандартный вход Стандартный выход
1
3
3 7 1
15 2 2
3 4 5
2187
50625
763327764

0.115s 0.018s 15