Bạn được cho một chiếc vòng cổ gồm ~n~ hạt. Mỗi hạt có thể được tô bằng màu bất kỳ trong ~m~ màu cho trước.

Hai vòng cổ được xem là giống nhau nếu có thể xoay vòng (theo chiều kim đồng hồ hoặc ngược chiều) một trong hai sao cho chúng trở nên giống hệt nhau.

Nhiệm vụ của bạn là đếm số vòng cổ khác nhau, không tính các vòng chỉ khác nhau do xoay vị trí.

Đầu vào:

Dòng duy nhất chứa hai số nguyên ~n~ và ~m~:

~n~: số lượng hạt trong vòng cổ.

~m~: số lượng màu có thể sử dụng.

Đầu ra:

In ra một số nguyên duy nhất là số vòng cổ khác nhau, lấy modulo ~10^9+7~

Ràng buộc:

~1 \le n,m \le 10^6~

Ví dụ :

Input:

4 3

Output:

24