ƯCLN của lũy thừa

Cho ba số nguyên dương \(A\), \(B\) và \(N\). Hãy tính ước chung lớn nhất của hai số \(A^N\) (tức là \(A\) nhân với chính nó \(N\) lần) và \(B\), ký hiệu \(\gcd(A^N, B)\).

Lưu ý rằng \(A^N\) có thể lớn hơn rất nhiều so với phạm vi biểu diễn của các kiểu số nguyên thông thường.

Input

Một dòng duy nhất chứa ba số nguyên \(A\), \(B\), \(N\) cách nhau bởi dấu cách.

Output

In ra một số nguyên duy nhất là giá trị \(\gcd(A^N, B)\).

Constraints

• \(1 \le A, B \le 10^9\)
• \(1 \le N \le 10^{15}\)

Sample Input 1

12 90 1

Sample Output 1

6

Sample Input 2

6 72 2

Sample Output 2

36

Explanation

• Ví dụ 1: \(12^1 = 12\) và \(\gcd(12, 90) = 6\).
• Ví dụ 2: \(6^2 = 36\) và \(\gcd(36, 72) = 36\).