题目描述

$\text{Mirko}$ 和 $\text{Slavko}$ 在玩一个游戏，先由 $\text{Mirko}$ 在 $1\dots N$ 中选出几组互质的数。例如当 $N=5$ 时，$\text{Slavko}$ 可以选择 $\big\{\{1,2\},\{3,4\},\{2,5\},\{3,5\},\cdots\big\}$ 中的几组。

然后轮到 $\text{Slavko}$。他需要找到一个 $x\in \big[2,n\big]$ 使得对于每组 $\{a,b\}$ 都满足以下两个条件之一：

• $a$，$b<x$

• $a$，$b\ge x$

例如，如果 $\text{Mirko}$ 选了 $\big\{\{1,2\},\{3,4\}\big\}$，那么 $x$ 可以等于 $3$。

如果 $\text{Slavko}$ 找不到满足条件的 $x$ 值，则表示 $\text{Mirko}$ 获得胜利。现在请你求出 $\text{Mirko}$ 获胜的不同情况的总数，在对 $10^9$ 取模后告诉他。

输入格式

第一行包含一个整数 $N$。

输出格式

第一行输出一个整数，为 $\text{Mirko}$ 获胜的不同情况的总数对 $10^9$ 取模后的值。

2

1

3

5

4

21

提示

【样例 1 解释】

$\text{Slavko}$ 只有一种取法 $\big\{\{1,2\}\big\}$。

【样例 2 解释】

$\text{Slavko}$ 的其中一种取法为 $\big\{\{1,2\},\{1,3\}\big\}$。

【数据范围】

对于 $100\%$ 的数据，$1\le N\le 20$。

【题目来源】

题目译自 COCI 2015-2016 CONTEST #6 T4 PAROVI。

本题分值按 COCI 原题设置，满分 $120$。