Hai từ a và b được gọi là giống nhau nếu a = b hoặc a = b^r, trong đó b^r là từ nhận được từ b bằng cách viết các ký tự theo trình tự ngược lại. Ví dụ, 'abcde' và 'edcba' là hai từ giống nhau, còn 'abb' và 'aba' - không giống nhau.

Yêu cầu: Tính số lượng tối đa các từ độ dài n từng cặp không giống nhau với bảng chữ cái k kí tự và đưa ra phần dư khi chia số đó cho 10⁹+7.

Ví dụ: với n = 3 và k = 2 ta có 6 từ không giống nhau từng đôi một: 'aaa', ',aab', 'aba', 'abb', 'bab', 'bbb'.

Dữ liệu: Vào từ file văn bản WORDS.INP gồm một dòng chứa 2 số nguyên n và k (1 ≤ n ≤ 10⁹, 1 ≤ k ≤ 10⁹).

Kết quả: Đưa ra file văn bản WORDS.OUT dưới dạng số nguyên.

Ví dụ:

WORDS.INP

3 2

WORDS.OUT

6