Mirko 和 Slavko 正在玩一个游戏。Mirko 先手，他选择一个非空的数对集合，数对中的数字在 $1$ 到 $N$（含）之间，且满足每个数对中的两个数互质。数对中的两个数必须不同。例如，对于 $N = 5$，Mirko 可以选择以下数对集合：$\{\{1, 2\}, \{3, 4\}, \{2, 5\}, \{3, 5\}\}$。

Slavko 后手，他的目标是为 Mirko 的数对集合找到一个“划分”。如果存在一个来自集合 $\{2, 3, \dots, N\}$ 的整数 $x$，使得对于每个数对 $\{a, b\}$，以下条件之一成立，则称 Mirko 的数对集合存在一个划分：

• $a, b < x$
• $a, b \ge x$

例如，数对集合 $\{\{1, 2\}, \{3, 4\}\}$ 拥有一个划分 $x = 3$。如果存在划分，Slavko 一定能找到它。

如果 Slavko 找不到他的集合的划分，Mirko 获胜。确定 Mirko 最初可以选择多少个不同的数对集合以确保自己获胜。由于总方案数可能非常大，请输出该数量模 $1\,000\,000\,000$ 的结果。

输入格式

输入的第一行包含一个整数 $N$（$1 \le N \le 20$）。

输出格式

输出的第一行也是唯一一行必须包含所需的数量。

样例

输入样例 1

2

输出样例 1

1

输入样例 2

3

输出样例 2

5

输入样例 3

4

输出样例 3

21

说明

样例 1 说明：唯一满足给定要求的数对集合是 $\{\{1, 2\}\}$。

样例 2 说明：满足给定要求的一个数对集合的例子是 $\{\{1, 3\}, \{1, 2\}\}$。