BéTậpĐi vừa chế được máy tính toán học gồm ba hàm đặc biệt:
Hàm thứ nhất là P(x) trả về tập hợp các ước nguyên tố của x. Ví dụ: P(15) = {3, 5}
Hàm thứ hai là factorize(x, p) trả về số nguyên pk lớn nhất sao cho x chia hết cho pk. Ví dụ: factorize(54, 3) = 27.
Hàm cuối cùng f(x, y) sẽ bằng tích của các factorize(y, p) với p thuộc tập hợp P(x). Ví dụ: f(18, 15) = factorize(15, 2) * factorize(15, 3); vì P(18) = {2, 3};
BéTậpĐi muốn viết hàm thứ tư g(x, n) = f(x, 1) * f(x, 2) * f(x, 3) * ... * f(x, n). Tuy nhiên, bé sợ máy tính chạy hàm quá lâu nên cần phải tối ưu thuật toán. Các bạn hãy giúp bé nhé!
INPUT: Gồm hai số nguyên dương duy nhất, lần lượt là x <= 10^9 và n <= 10^18.
OUTPUT: Gồm một số nguyên duy nhất là kết quả của hàm g(x, n) MOD 10^9+7
Bài có 2 subtask:
Subtask 1: x, n <= 10^4
Subtask 2: Như đề cho.
| INPUT | OUTPUT |
| 12 3 | 6 |
P(12) = {2, 3}
f(12, 1) = factorize(1, 2) * factorize(1, 3) = 1 * 1 = 1;
f(12, 2) = factorize(2, 2) * factorize(2, 3) = 2 * 1 = 2;
f(12, 3) = factorize(3, 2) * factorize(3, 3) = 1 * 3 = 3;
=> g(12, 3) = f(12, 1) * f(12, 2) * f(12, 3) = 1*2*3 = 6