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

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

Условие

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 2 ⋅ 105

0 ≤ a, b ≤ 109

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

Стандартный вход Стандартный выход
1
3
3 4
2 8
123 123
81
256
921450052

0.124s 0.015s 15