Xâu đối xứng và những thao tác

Xem PDF
Tác giả:
jumptozero
Dạng bài
Điểm: 600 Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

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

Test 1

Input 
3 2
Output 
8
Note

Giải thích: Ta có: \(S(3,2)=\left\{(1,2,1),(1,1,1),(2,2,2),(2,1,2)\right\}\), Khi đó có \(8\) dãy khác nhau có thể tạo ra đó là :\((1,2,1),(2,1,1),(1,1,2),(2,1,2),(1,2,2),(2,2,1),(1,1,1),(2,2,2)\). Vậy nên đáp án là \(8\).

Bình luận