/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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 を出力せよ。
入力例 1
2
出力例 1
1
K の値は 1 で、name-preserving であるような唯一の会員構成は \{\{1\}\} です (\{\{2\}\} はこれと同一とみなされます)。
入力例 2
3
出力例 2
1
K の値は 2 で、name-preserving であるような唯一の会員構成は \{\{1\}, \{1, 2\}\} です (置換により一致する会員構成を同一視すると、これのみです)。
入力例 3
4
出力例 3
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\}\}
入力例 4
13
出力例 4
6
入力例 5
26
出力例 5
-1
入力例 6
123456789123456789
出力例 6
-1
Score : 2400 points
Problem Statement
There are N people (with different names) and K clubs. For each club you know the list of members (so you have K unordered lists). Each person can be a member of many clubs (and also 0 clubs) and two different clubs might have exactly the same members. The value of the number K is the minimum possible such that the following property can be true for at least one configuration of clubs. If every person changes her name (maintaining the property that all names are different) and you know the new K lists of members of the clubs (but you don't know which list corresponds to which club), you are sure that you would be able to match the old names with the new ones.
Count the number of such configurations of clubs (or say that there are more than 1000). Two configurations of clubs that can be obtained one from the other if the N people change their names are considered equal.
Formal statement: A club is a (possibly empty) subset of \{1,\dots, N\} (the subset identifies the members, assuming that the people are indexed by the numbers 1, 2,\dots, N). A configuration of clubs is an unordered collection of K clubs (not necessarily distinct). Given a permutation \sigma(1), \dots, \sigma(N) of \{1,\dots, N\} and a configuration of clubs L=\{C_1, C_2, \dots, C_K\}, we denote with \sigma(L) the configuration of clubs \{\sigma(C_1), \sigma(C_2), \dots, \sigma(C_K)\} (if C is a club, \sigma(C)=\{\sigma(x):\, x\in C\}). A configuration of clubs L is name-preserving if for any pair of distinct permutations \sigma\not=\tau, it holds \sigma(L)\not=\tau(L).
You have to count the number of name-preserving configurations of clubs with the minimum possible number of clubs (so K is minimum). Two configurations L_1, L_2 such that L_2=\sigma(L_1) (for some permutation \sigma) are considered equal. If there are more than 1000 such configurations, print -1.
Constraints
- 2 \le N \le 2\cdot10^{18}
Input
The input is given from Standard Input in the format
N
Output
If ans is the number of configurations with the properties described in the statement, you should print on Standard Output
ans
If there are more than 1000 such configurations, print -1.
Sample Input 1
2
Sample Output 1
1
The value of K is 1 and the unique name-preserving configuration of clubs is \{\{1\}\} (the configuration \{\{2\}\} is considered the same).
Sample Input 2
3
Sample Output 2
1
The value of K is 2 and the unique (up to permutation) name-preserving configuration of clubs is \{\{1\}, \{1, 2\}\}.
Sample Input 3
4
Sample Output 3
7
The value of K is 3 and the name-preserving configurations of clubs with 3 clubs are:
- \{\{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\}\}
Sample Input 4
13
Sample Output 4
6
Sample Input 5
26
Sample Output 5
-1
Sample Input 6
123456789123456789
Sample Output 6
-1