Ngày Valentine sắp tới nên Vũ dự định làm một bông hoa hướng dương thật to bằng gỗ để tỏ tình với người yêu. Bông hoa này sẽ có nhụy hoa hình tròn với \(n\) cánh hoa cách đều nhau và mỗi cánh sẽ được sơn một trong \(m\) màu. Biết người yêu thích màu sắc nên Vũ sẽ sơn sao cho không có \(2\) cánh hoa kề nhau nào mà có màu giống nhau.

Vũ tự hỏi là sẽ có bao nhiêu bông hoa có thể được tạo. Hãy trả lời giúp Vũ nhé.

Lưu ý: Hai bông hoa được gọi là khác nhau nếu chúng có ít nhất một cánh hoa có màu khác nhau (không xét đến phép quay hay lật).

Input

• Gồm một dòng chứa hai số nguyên dương \(n\) và \(m\) (\(n \le 10^{18}, m \le 10^9\)).

Output

• In ra một số nguyên duy nhất là số lượng bông hoa có thể tạo được sau khi lấy dư cho \(10^9+7\).

Example

3 4

24

4 3

18

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(n \le 100, m \le 100\).
• Subtask \(2\) (\(60\%\) số điểm): Không có ràng buộc gì thêm.