Ancient Pig Script

The civilization of the Pig Kingdom is long-standing and profound.

iPig, while researching in the library of the Big Pig School, learned that the total number of ancient pig characters was $N$. Naturally, if a language has many characters, its dictionary will be correspondingly large. The king of the Pig Kingdom at that time considered that if a dictionary were to be compiled, its scale might far exceed that of the Kangxi Dictionary, and the pig-power and material resources required would be immeasurable. Therefore, after much deliberation, he did not carry out this labor-intensive and wealth-draining endeavor. Of course, the characters of the Pig Kingdom were gradually simplified over the course of history, with some infrequently used characters being removed.

iPig intends to study the pig script of a certain dynasty in ancient times. According to relevant historical documents, the pig script passed down from that dynasty was exactly $1/k$ of the ancient total, where $k$ is a positive divisor of $N$ (which can be $1$ or $N$). However, due to the passage of time, it is impossible to verify exactly which $1/k$ it was, or what $k$ is.

iPig believes that every $k$ that divides $N$ is possible as long as it is consistent with the documents. He intends to consider all possible values of $k$. Obviously, when $k$ is a fixed value, the number of pig characters in that dynasty is $N/k$. However, there are also many ways to choose $N/k$ characters from $N$ characters. iPig estimates that if the sum of the number of ways for all possible $k$ is $P$, then the cost of his research into the ancient script will be $G^P$.

Now he wants to know the cost of researching the ancient script of the Pig Kingdom. Since iPig feels this number might be astronomical, you only need to tell him the remainder of the answer when divided by $999911659$.

Input

The input contains only one line: two integers $N$ and $G$, separated by a space.

Output

The output contains only one line: a single integer, representing the remainder of the answer when divided by $999911659$.

Examples

Input 1

4 2

Output 1

2048

Constraints

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 100000$; For $100\%$ of the data, $1 \le G \le 1000000000$, $1 \le N \le 1000000000$.