Mô tả

Tết Trung thu đang đến gần, bé Na muốn trang trí cửa sổ phòng mình bằng một dãy đèn thật đẹp. Bé có ~n~ chiếc bóng đèn nhỏ xinh và một hộp màu kỳ diệu với ~k~ màu sắc lung linh khác nhau. Mỗi bóng đèn có thể được tô một màu bất kỳ từ hộp màu của bé. Bé Na rất tò mò không biết mình có thể tạo ra bao nhiêu kiểu dãy đèn khác nhau để trang trí cửa sổ nhỉ?

Hãy giúp bé Na tính xem có tất cả bao nhiêu cách để tạo ra những dãy đèn độc đáo và khác nhau. Vì số có thể rất lớn, hãy in ra kết quả sau khi chia lấy dư cho ~(10^9 + 7)~.

Lưu ý: Hai dãy đèn được coi là khác nhau nếu có ít nhất một vị trí mà hai dãy có màu khác nhau.

Input

Một dòng duy nhất gồm hai số nguyên dương ~n~, ~k~ ~(1 ≤ n, k ≤ 10^{18})~ ~-~ số lượng bóng đèn của bé Na và số lượng màu trong hộp màu kỳ diệu.

Output

Một số nguyên duy nhất là số cách tô màu khác nhau có thể có sau khi chia lấy dư cho ~(10^9 + 7)~.

Tính điểm

Ví dụ

Input

2 2

Output

4