{"problem":{"name":"Rotated Palindromes","description":{"content":"Takahashi and Aoki are going to together construct a sequence of integers. First, Takahashi will provide a sequence of integers $a$, satisfying all of the following conditions: *   The length of $a$ ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc064_d"},"statements":[{"statement_type":"Markdown","content":"Takahashi and Aoki are going to together construct a sequence of integers.\nFirst, Takahashi will provide a sequence of integers $a$, satisfying all of the following conditions:\n\n*   The length of $a$ is $N$.\n*   Each element in $a$ is an integer between $1$ and $K$, inclusive.\n*   $a$ is a _palindrome_, that is, reversing the order of elements in $a$ will result in the same sequence as the original.\n\nThen, Aoki will perform the following operation an arbitrary number of times:\n\n*   Move the first element in $a$ to the end of $a$.\n\nHow many sequences $a$ can be obtained after this procedure, modulo $10^9+7$?\n\n## Constraints\n\n*   $1≤N≤10^9$\n*   $1≤K≤10^9$\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $K$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc064_d","tags":[],"sample_group":[["4 2","6\n\nThe following six sequences can be obtained:\n\n*   $(1, 1, 1, 1)$\n*   $(1, 1, 2, 2)$\n*   $(1, 2, 2, 1)$\n*   $(2, 2, 1, 1)$\n*   $(2, 1, 1, 2)$\n*   $(2, 2, 2, 2)$"],["1 10","10"],["6 3","75"],["1000000000 1000000000","875699961"]],"created_at":"2026-03-03 11:01:14"}}