Ancient Pig Characters

Pig Kingdom is an ancient civilization with a long and profound history. In the ancient times there were \(n\) characters in the pig script. However, when the kingdom decided to simplify the script during a certain dynasty, only \(\frac{1}{k}\) of the original characters were retained, where \(k\) is a positive divisor of \(n\) (\(k\) can be 1 or \(n\) as well). In other words, if one fixes a divisor \(k\) of \(n\), then the dynasty's script has \(\frac{n}{k}\) characters. Since the surviving characters were chosen from the original \(n\) characters, there are \(\binom{n}{\frac{n}{k}}\) possible selections for that particular divisor.

Because every divisor \(k\) of \(n\) is a candidate (according to the documents), the total number of possible cases is \[ p = \sum_{k\mid n} \binom{n}{n/k}. \] The research cost of studying the ancient characters is then defined as \(g^p\). Since \(g^p\) can be extremely large, you are only required to output the cost modulo \(999911659\).

Important note: If \(n \ge 999911659\), then it can be shown that \(p\) is a multiple of \(999911658\) (using properties of binomial coefficients), so in that case the answer is 0.

Given two integers \(n\) and \(g\), compute \(g^p \bmod 999911659\).

inputFormat

The input consists of a single line containing two integers \(n\) and \(g\) separated by a space.

\(1 \le n, g \le 10^9\) (In practice, if \(n \ge 999911659\), output 0 according to the note.)

outputFormat

Output a single integer, the value of \(g^p\) modulo \(999911659\), where \(p = \sum_{{k\mid n}} \binom{n}{n/k}\).

sample

4 2

2048