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

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

Обмеження

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

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

У першому рядку вхідних даних є ціле число \(n\) : кількість обчислень.

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

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

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

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

3
3 7 1
15 2 2
3 4 5

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

2187
50625
763327764