Ваше завдання — ефективно обчислити значення ~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