In this problem, we try to compute discrete k^th root modulo n; given n, k, a; find all the solutions for x such that x^k = a (mod n) and x is coprime with n.

Input

For each input file, there are 3 space separated integers n, k, a.

n = p^e for some odd prime p, integer e > 0; 0 <= a < n <= 10⁹, 0 <= k < phi(n), where phi is Euler's totient function; the numbers n, a are coprimes.

Output

The first line of the output contains a single integer m, the number of solutions in the range [0, n - 1] that are coprimes with n, followed by m lines that contain the m solutions in ascending order. It is guaranteed that m <= 10⁴.

Example

Input:
5 1 3

Output:
1
3