Description

Original source: SDOI 2010

The civilization of the Pig Kingdom is profound and extensive.

iPig was researching in the Fat Pig School Library and discovered that the total number of ancient Pig script characters was $N$. Of course, if a language has many characters, its dictionary would correspondingly be very large. The king of the Pig Kingdom at that time considered that compiling such a dictionary might far exceed the scale of the Kangxi Dictionary, and the labor and resources required would be incalculable. After careful consideration, the king decided not to undertake this laborious and costly project. Naturally, the Pig script was later simplified over time, with some less commonly used characters removed.

iPig intends to study the Pig script of a certain dynasty from ancient times. According to relevant historical records, the Pig script passed down from that dynasty was exactly $\frac{1}{k}$ of the ancient script, where $k$ is a positive divisor of $N$ (which could be $1$ or $N$). However, exactly which $\frac{1}{k}$ it was, and what $k$ was, are lost to history due to the passage of time.

iPig believes that as long as it aligns with the historical records, every possible $k$ that divides $N$ is plausible. He plans to consider all possible $k$. Clearly, when $k$ is fixed, the number of Pig script characters from that dynasty would be $\frac{N}{k}$. However, there are also numerous ways to preserve $\frac{N}{k}$ characters out of $N$. iPig estimates that if the sum of all possible cases for all possible $k$ is $P$, then the cost of his research into the ancient script would be $G$ raised to the power of $P$.

Now he wants to know the cost of researching the ancient script for the Pig Kingdom. Since iPig suspects this number might be astronomically large, you only need to provide the remainder when the answer is divided by $999911659$.

Input Format

The input consists of exactly one line: two numbers $N$ and $G$, separated by a space.

Output Format

The output consists of exactly one line: a number representing the remainder when the answer is divided by $999911659$.

Sample 1

4 2

2048

Data Range and Hints

For $10\%$ of the data, $1\le N\le 50$;

For $20\%$ of the data, $1\le N\le 1000$;

For $40\%$ of the data, $1\le N\le 10^5$;

For $100\%$ of the data, $1\le G\le 10^9$, $1\le N\le 10^9$.