Ваше завдання — ефективно обчислити значення ~a^b~ за модулем ~10^9+7~.

Зверніть увагу, що в цьому завданні ми припускаємо, що ~0^0=1~.

Обмеження

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

Формат вхідних даних

Перший рядок містить ціле число ~n~: кількість обчислень.

Після цього є ~n~ рядків, кожен з яких містить два цілих числа ~a~ і ~b~.

Формат вихідних даних

Виведіть кожне значення ~a^b~ за модулем ~10^9+7~.

Приклад вхідних даних

3
3 4
2 8
123 123

Приклад вихідних даних

81
256
921450052