配点 : $2400$ 点

問題文

$N$ 人の (名前の異なる) 人がおり、$K$ 個のクラブがあります。あなたは、各クラブの会員をすべて知っています (形式的に言えば、$K$ 個の無順序リストを持っています)。それぞれの人は複数のクラブの会員である可能性も、どのクラブの会員でもない可能性もあります。複数のクラブの会員の集合が全く同じである可能性もあります。 ここで、$K$ の値は、次の条件を満たす会員構成が少なくとも一通り存在するような最小の値となっています。

• $N$ 人全員が (全員の名前が異なるという条件を守りながら) 改名して、$K$ 個のクラブの改名後の会員リストがあなたに与えられた (ただし、どの会員リストがどのクラブのものかは知らされない) とする。このとき、あなたは確実に、改名後の $N$ 個の名前すべてについてその名前の人の元の名前を当てることができる。

このような $K$ 個のクラブの会員構成が何種類存在するか求めてください。ただし、$1000$ 種類を超える場合はその旨を報告してください。 ここで、$2$ 種類の会員構成は、一方において $N$ 人の人が適切に改名することでもう一方が得られるなら同一とみなします。

厳密な問題文: クラブとは、$\{1,\dots, N\}$ の部分集合 (空である可能性もある) である。($N$ 人の人に番号 $1, 2, \ldots, N$ が付けられているとすると、この集合の要素がクラブの会員に対応する。) 会員構成とは、$K$ 個のクラブ (異なるとは限らない) からなる多重集合である。 $\{1,\dots, N\}$ の順列 $\sigma(1), \dots, \sigma(N)$ と会員構成 $L=\{C_1, C_2, \dots, C_K\}$ に対し、$\sigma(L)$ で会員構成 $\{\sigma(C_1), \sigma(C_2), \dots, \sigma(C_K)\}$ を表す ($C$ がクラブであるとき、$\sigma(C)=\{\sigma(x):\, x\in C\}$ である)。 会員構成 $L$ は、任意の異なる順列 $\sigma\not=\tau$ に対して $\sigma(L)\not=\tau(L)$ を満たすとき、name-preserving であるという。

name-preserving であってクラブ数 $K$ が最小であるような会員構成の個数を求めよ。ある順列 $\sigma$ が存在して $L_2=\sigma(L_1)$ が成立するような $2$ つの会員構成 $L_1, L_2$ は同一とみなす。このような会員構成の個数が $1000$ を超える場合は $-1$ を出力せよ。

制約

• $2 \le N \le 2\cdot10^{18}$

入力

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

$N$

出力

問題文で述べたような会員構成が $ans$ 種類存在するとして、以下の形式で標準出力に出力せよ。

$ans$

ただし、このような会員構成の数が $1000$ 種類より多い場合は $-1$ を出力せよ。

2

1

$K$ の値は $1$ で、name-preserving であるような唯一の会員構成は $\{\{1\}\}$ です ($\{\{2\}\}$ はこれと同一とみなされます)。

3

1

$K$ の値は $2$ で、name-preserving であるような唯一の会員構成は $\{\{1\}, \{1, 2\}\}$ です (置換により一致する会員構成を同一視すると、これのみです)。

4

7

$K$ の値は $3$ で、name-preserving であるような $3$ クラブの会員構成は以下の通りです。

• $\{\{1\}, \{2\}, \{1, 3\}\}$
• $\{\{1\}, \{1, 2\}, \{2, 3\}\}$
• $\{\{1, 2\}, \{1, 2\}, \{1, 3\}\}$
• $\{\{1\}, \{1, 2\}, \{1, 2, 3\}\}$
• $\{\{1\}, \{2, 3\}, \{1, 2, 4\}\}$
• $\{\{1, 2\}, \{1, 3\}, \{1, 2, 4\}$
• $\{\{1, 2\}, \{1, 2, 3\}, \{2, 3, 4\}\}$

13

6

26

-1

123456789123456789

-1