Gọi \(S(n,k)\) là tập hợp tất cả dãy đối xứng gồm \(n\) phần tử, mỗi phần tử thuộc đoạn \([1;k](k\in \mathbb{N}^{*})\) . (Dãy đối xứng là dãy mà khi ta viết ngược hay viết xuôi thì đều như nhau).

Ví dụ \(S(3,2)=\left\{(1,2,1),(1,1,1),(2,2,2),(2,1,2)\right\}\).

Henry và Kaninho lần lượt thực hiện thủ tục như sau:

• Mỗi lượt, Henry sẽ lấy một dãy \(T\) từ tập \(S(n,k)\) rồi đưa cho Kaninho. Sau đó Kaninho sẽ thực hiện thao tác sau với số lần bất kì: Di chuyển phần tử đầu tiên của dãy đến sau phần tử cuối cùng của dãy.

Hỏi sau khi hoàn thiện các thủ tục trên, thì số dãy khác nhau tối đa có thể tạo ra là bao nhiêu ?

Vì đáp án có thể lớn nên kết quả cần lấy mod \(10^9+7\) trước khi in ra.

Input

• Dòng thứ nhất chứa hai số nguyên \(n,k(1\le n,k\le 10^9)\)

Output

• Đáp án cần tìm

Example

3 2

8