G - Simple Math Problem 2

問題文

正整数 $M$ が与えられます。 $0 \le x < M$ を満たす整数 $x$ であって、 $x^3 \equiv x \pmod M$ を満たすものをすべて求めてください。

制約

• $1 \le M \le 10^{12}$
• $M$ は整数

入力

入力は以下の形式で標準入力から与えられる。

出力

条件を満たす $x$ がちょうど $K$ 個あるとし、それを $A_1, A_2, \cdots, A_K$ （ $i \ne j$ なら $A_i \ne A_j$ ）とする。

$1$ 行目には、 $K$ を出力せよ。

$2$ 行目には、 $A_1, A_2, \dots, A_K$ を空白区切りで昇順に出力せよ。

注意

この問題の制約下で、出力すべき値の個数は $3 \times 10^5$ 以下であることが証明される。

サンプル1

5

3
0 1 4

サンプル2

1

1
0

サンプル3

20

9
0 1 4 5 9 11 15 16 19

$2$ 行目は昇順に出力する必要があることに注意してください。