Vòng màu dưới phép quay · canuc80k7209

Description

Một vòng cổ có $n$ hạt, mỗi hạt chọn một trong $m$ màu ( $1 \leq n, m \leq 1 0^{6}$ ). Hai cách tô được xem là cùng một vòng cổ nếu có thể quay vòng một cách để trùng khít.

Đếm số lớp tương đương dưới phép quay và in modulo $1000000007$ .

Input

Một dòng chứa $n$ $m$ .

Output

In kết quả theo yêu cầu, lấy modulo như đã nêu trong phần mô tả.

Constraints

$1 \leq n, m \leq 1 0^{6}$ .

Scoring

Subtask $1$ ( $50%$ số điểm): các test nhỏ trong $10$ test đầu của bộ dữ liệu.
Subtask $2$ ( $50%$ số điểm): không có giới hạn bổ sung.

Example

Test 1

Input

1 1

Output

Giải thích: Một hạt với một màu chỉ tạo ra một vòng cổ, bất kể xét phép quay.

Phân tích: Nhóm có n phép quay. Theo Burnside, số quỹ đạo bằng trung bình số cách tô được cố định bởi mỗi phép quay.
Phân tích: Quay k vị trí phân hoạch các hạt thành gcd(n,k) chu trình. Một cách tô được giữ nguyên khi mọi hạt trong cùng chu trình có cùng màu, nên có m^{gcd(n,k)} cách.
Phân tích: Do đó
Phân tích: ans = (1/n) ∑_{k=0}^{n-1} m^{gcd(n,k)}.
Phân tích: Để không lặp n lần, gom các k có cùng gcd. Với d|n, số k sao cho gcd(n,k)=d là φ(n/d). Vì vậy
Phân tích: ans = (1/n) ∑_{d|n} φ(n/d)·m^d.
Phân tích: Liệt kê ước theo cặp, tính φ bằng phân tích thừa số và dùng lũy thừa nhanh. Nhân tổng với n^{-1} modulo prime.
Thuật toán: Cài đặt trực tiếp công thức hoặc quy hoạch nêu trên, tiền xử lý các đại lượng tổ hợp cần thiết và chuẩn hóa mọi phép toán theo modulo của đề. Các trường hợp không khả thi được loại trước khi thực hiện phép chia modulo.
Chứng minh: Burnside đảm bảo trung bình số điểm cố định bằng số quỹ đạo. Công thức số chu trình của phép quay xuất phát từ các quỹ đạo i,i+k,i+2k,..., có đúng gcd(n,k) chu trình. Việc gom theo ước chỉ tái lập chỉ số tổng, nên không thay đổi giá trị.
Độ phức tạp: Khoảng O(τ(n)·(log m + √n)) với cách phân tích trực tiếp; bộ nhớ O(τ(n)).