{"raw_statement":[{"iden":"problem statement","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$?"},{"iden":"constraints","content":"*   $1≤N≤10^9$\n*   $1≤K≤10^9$"},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $K$"},{"iden":"sample input 1","content":"4 2"},{"iden":"sample output 1","content":"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)$"},{"iden":"sample input 2","content":"1 10"},{"iden":"sample output 2","content":"10"},{"iden":"sample input 3","content":"6 3"},{"iden":"sample output 3","content":"75"},{"iden":"sample input 4","content":"1000000000 1000000000"},{"iden":"sample output 4","content":"875699961"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}