P2480 [SDOI2010] Ancient Pig Script

"Beyond those mountains and beyond those seas lives a group of little chubby pigs. They are lively and clever, naughty yet quick. They live freely on that vast green lawn, kind and brave, caring for one another..." — From the national anthem of the Pig Kingdom. A long time ago, in a blessed land beyond the mountains and seas, there once existed a Pig Kingdom. The Pig Kingdom was in a remote location and adopted a self-sufficient manor economy suited to its time, with little contact with the outside world and even fewer commercial activities. As a result, few other animals knew of such a kingdom. Although the Pig Kingdom was not large, its land was fertile and its houses were well ordered. If one had to compare it to something, it could only be the imagined Peach Blossom Spring described by Tao Yuanming of the Eastern Jin. The Pig King governed diligently and loved his people; the pig citizens lived and worked in peace and contentment; neighbors got along harmoniously; the country was orderly; the economy thrived; and society was harmonious and stable. Such harmony inspired in the pig citizens a fiery passion for work and a rosy vision for the future. The little pig iPig was an ordinary citizen of the Pig Kingdom. He was 10 years old this year and in the third grade at Big Fat Pig Elementary School. Like most pigs, he was not very smart, so he often ran into problems that were either odd or seemed trivial to others, giving him big headaches. Later, he took part in the Pig Olympiad in Informatics (POI), achieved a good ranking, and was finally recommended for admission to Pig Kingdom University (PKU) for further study. Now iPig can use a computer to solve simple problems, such as writing a program in the P++ language to compute the value of $A + B$. This “achievement” has become a favorite topic of his. Of course, classmates who do not know the full story have begun to look at him with new respect. iPig’s story begins here and will accompany everyone for two days. We hope you will enjoy it.

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$.

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

Output one line containing a single integer representing the answer.

- 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