Một vòng cổ gồm \(n\) hạt, mỗi hạt có thể tô một trong \(k\) màu. Hai vòng cổ được coi là giống nhau nếu có thể xoay vòng để trùng nhau. Đếm số vòng cổ phân biệt modulo \(10^9+7\).

Dùng Burnside's lemma: số cách = \(\frac{1}{n} \sum_{i=0}^{n-1} k^{\gcd(i, n)}\).

Định dạng đầu vào

• Một dòng chứa hai số nguyên \(n, k\) (\(1 \le n, k \le 10^5\)).

Định dạng đầu ra

• Một số nguyên là số vòng cổ phân biệt modulo \(10^9+7\).

Ví dụ

Input:

4 2

Output:

6

Giải thích: 4 hạt, 2 màu, có 6 vòng cổ phân biệt (xoay).

Ràng buộc

• 100% số điểm: \(n \le 10^5\).