{"code":"palikanhen","name":"Xâu đối xứng và những thao tác","description":"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).\r\n\r\nVí dụ $S(3,2)=\\left\\{(1,2,1),(1,1,1),(2,2,2),(2,1,2)\\right\\}$.\r\n\r\n**Henry** và **Kaninho** lần lượt thực hiện thủ tục như sau:\r\n\r\n+ 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.\r\n\r\n\r\nHỏ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 ? \r\n\r\nVì đáp án có thể lớn nên kết quả cần lấy mod $10^9+7$ trước khi in ra.\r\n\r\n#### Input\r\n+ Dòng thứ nhất chứa hai số nguyên $n,k(1\\le n,k\\le 10^9)$\r\n\r\n#### Output\r\n+ Đáp án cần tìm\r\n\r\n#### Example\r\n!!! question \"Test 1\"\r\n\r\n    ???+ \"Input\"\r\n\r\n        ```sample\r\n        3 2\r\n        ```\r\n\r\n    ???+ success \"Output\"\r\n\r\n        ```sample\r\n        8\r\n        ```\r\n        \r\n    ??? warning \"Note\"\r\n\r\n        **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$.","points":600.0,"partial":false,"time_limit":2.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}