Дано \(q\) запитів, що складаються з трьох цілих чисел \(a\), \(b\), \(c\). Для кожного запиту знайдіть значення \(a^{b^c}\) за модулем \(10^9+7\).

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

Input Specification

Перший рядок містить ціле число \(q\) \((1 \le q \le 10^5)\) - кількість запитів.

Кожен з наступних \(q\) рядків містить по 3 цілі числа \(a\), \(b\) та \(c\) \((0 \le a, b, c \le 10^9)\).

Output Specification

Виведіть відповіді для кожного запиту в окремому рядку.

Sample Input 1

3
3 7 1
15 2 2
3 4 5

Sample Output 1

2187
50625
763327764