Có ~n~ cọc hàng rào được xếp thẳng hàng và ~k~ màu sơn khác nhau. Bạn cần sơn các cọc sao cho không có quá 2 cọc liên tiếp cùng màu. Hãy tính số cách sơn hợp lệ.

Yêu cầu: Tính và đưa ra số cách sơn hợp lệ cho ~n~ cọc hàng rào.

Input

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

Output

In ra số cách sơn thõa mãn yêu cầu, lấy modulo ~10^9+7~.

Scoring

• Subtask ~1~ ~(45\%)~: ~n,k \leq 1000~;
• Subtask ~2~ ~(55\%)~: ~n,k \leq 10^5~.

Example input 1

3 2

Example output 1

6

Note 1

• Với ~n~= 3, ~k~ = 2 (hai màu: A, B):
  • AAB, ABA, ABB, BAA, BAB, BBA → tổng cộng có 6 cách.
• Không được có AAA hoặc BBB vì có 3 cọc cùng màu liên tiếp.