问题描述

有 $N$ 个人（具有不同的名字）和 $K$ 个俱乐部。对于每个俱乐部，您知道成员的名单（因此您有 $K$ 个无序列表）。每个人可以是许多俱乐部的成员（也可以是 $0$ 个俱乐部的成员），而且两个不同的俱乐部可能恰好有相同的成员。数值 $K$ 的值是最小可能的，以便下述属性至少对于一个俱乐部配置为真。如果每个人都更改自己的名字（保持所有名称都不同的属性），并且您知道俱乐部成员的新的 $K$ 个名单（但不知道哪个名单对应哪个俱乐部），则您可以确保能够将旧名字与新名字匹配。

计算这样的俱乐部配置的数量（或者说超过 $1000$ 个）。如果可以通过更改 $N$ 个人的名称从一个获得另一个的两个俱乐部配置被认为是相等的。

正式陈述：俱乐部是 $\\{1,\\dots, N\\}$ 的（可能为空）子集（假设按照数字 $1, 2,\\dots, 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\\}$）。如果对于任何不同的排列对 $\\sigma\\not=\\tau$，都有 $\\sigma(L)\\not=\\tau(L)$，则俱乐部配置 $L$ 是保持名称的。

您必须计算具有最小可能俱乐部数量的保持名称的俱乐部配置的数量（即 $K$ 最小）。被认为是相等的两个配置 $L_1, L_2$ 满足 $L_2=\\sigma(L_1)$（其中 $\\sigma$ 是某个排列）。如果有超过 $1000$ 个这样的配置，则输出 $-1$。

约束条件

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

---

输入

输入以标准输入格式给出

$N$

输出

如果 $ans$ 是满足陈述中描述的属性的配置数量，则应将其打印到标准输出

$ans$

如果有超过 $1000$ 个这样的配置，则输出 $-1$。

---

示例输入 1

2

示例输出 1

1

$K$ 的值为 $1$，唯一的名称保持配置的俱乐部是 $\\{\\{1\\}\\}$（被认为与配置 $\\{\\{2\\}\\}$ 相同）。

---

示例输入 2

3

示例输出 2

1

$K$ 的值为 $2$，唯一（经过排列后）的名称保持配置的俱乐部是 $\\{\\{1\\}, \\{1, 2\\}\\}$。

---

示例输入 3

4

示例输出 3

7

$K$ 的值为 $3$，具有 $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