Discrete Root

已知 $k, a, p$，求同余方程

$$x^{k}\equiv a\pmod p$$

的所有根，其中根的范围为 $[0, p-1]$，$p$ 为质数。

输入格式

一行三个整数 $p, k, a$。

输出格式

第一行一个整数，表示符合条件的 $x$ 的个数。

第二行开始每行一个数，表示符合条件的 $x$，按从小到大的顺序输出。

样例输入

11 3 8

样例输出

1
2

样例解释

$p=11$、$k=3$、$a=8$ 时，$2^{3}=8\equiv 8\pmod{11}$，而 $[0,10]$ 中其他的 $x$ 都不满足 $x^{3}\equiv 8\pmod{11}$，因此只有一个根 $x=2$。

数据范围

• $0\le a<p\le 10^9$，且 $p$ 为质数；
• $2\le k\le 10^5$。

来源与许可

本题题面与测试数据整理自 BZOJ 1420。

样例 1

输入

11 3 8

输出

1
2