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

Условие

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 2 ⋅ 10⁵

0 ≤ a, b ≤ 10⁹

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

3
3 4
2 8
123 123

81
256
921450052