Description

The civilization of the Pig Kingdom has a long history and great depth.

In the library of Big Fat Pig School, iPig learned from reference materials that the total number of characters in the ancient pig script was $n$. Of course, if a language has many characters, its dictionary will be correspondingly large. The Pig King of that time considered that if a dictionary were compiled, its scale might far exceed the Kangxi Dictionary, and the manpower and material resources required would be immeasurable. After careful consideration, he did not undertake this labor- and resource-intensive project. Naturally, the script of the Pig Kingdom was later simplified over history by removing some uncommon characters.

iPig plans to study the pig script from a certain dynasty in ancient times. According to relevant documents, the characters used in that dynasty happened to be exactly $1/k$ of those in the distant past, where $k$ is a positive divisor of $n$ (it can be $1$ or $n$). However, exactly which $1/k$ was used, and what $k$ was, can no longer be verified due to the remoteness of history.

iPig believes that as long as it matches the documents, every $k \mid n$ is possible. He will consider all possible $k$. Clearly, when $k$ is fixed, the number of characters in that dynasty’s script is $n/k$. However, the number of ways to retain $n/k$ characters out of $n$ is also quite large. iPig estimates that if the total number of cases over all possible $k$ sums to $p$, then the cost of his research on the ancient script will be $g^p$.

He now wants to know the cost for the Pig Kingdom to study the ancient script. Since iPig thinks this number may be astronomical, you only need to tell him the remainder of the answer modulo $999911659$.

Input Format

One line containing two positive integers $n, g$.

Output Format

Output one line containing a single integer representing the answer.

4 2

2048

Hint

• Constraints
  • For $10\%$ of the testdata, $1 \le n \le 50$.
  • For $20\%$ of the testdata, $1 \le n \le 1000$.
  • For $40\%$ of the testdata, $1 \le n \le 10^5$.
  • For $100\%$ of the testdata, $1 \le n, g \le 10^9$.

Translated by ChatGPT 5