G. Dãy số GCD
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Chung rất lười ra đề nhưng vì bị chích điện tâm huyết với BKCC#2, Chung quyết định ra một bài toán rất dễ như sau:

Với hai số nguyên dương $$$T$$$, Chung định nghĩa dãy $$$a$$$ vô hạn phần tử, đánh số từ $$$0$$$, theo nguyên tắc sau:

  • $$$a_0 = a_1 = T$$$.
  • $$$a_i$$$ = $$$\gcd(a_0 \times a_1 \times \cdots \times a_{\lfloor\frac{i}{2}\rfloor - 1}, a_{\lfloor\frac{i}{2}\rfloor} \times \cdots \times a_{i-1})$$$ $$$(\forall i \ge 2)$$$.

Mỗi bộ testcase, Chung cho bạn hai số nguyên dương $$$T, n$$$ và bạn được yêu cầu tính giá trị của $$$a_n$$$ với T được cho, chia lấy dư cho $$$10^9 + 7$$$.

Input

Dòng đầu tiên chứa số nguyên dương $$$t$$$ ($$$t \le 10^4$$$) — số testcase.

$$$t$$$ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương $$$T, n$$$ ($$$2 \le T \le 10^9, 2 \le n \le 10^6$$$) — Dữ liệu của bài toán.

Dữ liệu bài toán đảm bảo rằng tổng $$$n$$$ trong mọi testcase không vượt quá $$$10^6$$$.

Output

Mỗi testcase in ra một số nguyên dương — đáp án của bài toán.

Example
Input
1
5 6
Output
125
Note

Với $$$T = 5$$$, dãy số $$$a$$$ như sau: $$$5, 5, 5, 5, 25, 25, 125$$$.