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

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

Обмеження

• \(1≤n≤2⋅10^5\)
• \(0≤a,b≤10^9\)

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

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

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

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

Вивести кожне значення \(a^b\) по модулю \(10^9 + 7\) .

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

3
3 4
2 8
123 123

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

81
256
921450052