DISCRT - Discrete Roots

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

Input

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

n = pe for some odd prime p, integer e > 0; 0 <= a < n <= 109, 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 <= 104.

Example

Input:
5 1 3

Output:
1
3

Added by:Mostafa mahmoud
Date:2013-02-22
Time limit:0.200s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C CSHARP C++ 4.3.2 CPP GO JAVA PHP PYTHON PYPY PYTHON3
Resource:http://acm.sgu.ru/problem.php?problem=261

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.