Problem Description

$\text{Mirko}$ and $\text{Slavko}$ are playing a game. First, $\text{Mirko}$ chooses several pairs of coprime numbers from $1 \dots N$ (he must choose at least one pair, and the two numbers in each pair must be different). For example, when $N = 5$, $\text{Mirko}$ can choose some pairs from $\big\{\{1,2\},\{3,4\},\{2,5\},\{3,5\},\cdots\big\}$.

Then it is $\text{Slavko}$'s turn. He needs to find an $x \in \big[2, N\big]$ such that for every pair $\{a,b\}$, one of the following two conditions holds:

• $a$, $b < x$.

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

For example, if $\text{Mirko}$ chooses $\big\{\{1,2\},\{3,4\}\big\}$, then $x$ can be $3$.

If $\text{Slavko}$ cannot find a value of $x$ that satisfies the condition, then $\text{Mirko}$ wins. Now compute the total number of different choices for which $\text{Mirko}$ wins, and output it modulo $10^9$.

Input Format

The first line contains an integer $N$.

Output Format

Output one integer: the number of different choices for which $\text{Mirko}$ wins, modulo $10^9$.

2

1

3

5

4

21

Hint

Sample 1 Explanation

$\text{Slavko}$ has only one choice: $\big\{\{1,2\}\big\}$.

Sample 2 Explanation

One possible choice for $\text{Slavko}$ is $\big\{\{1,2\},\{1,3\}\big\}$.

Constraints

For $100\%$ of the testdata, $1 \le N \le 20$.

Source

Translated from COCI 2015-2016 CONTEST #6 T4 PAROVI.

This problem uses the original COCI scoring, with full score $120$.

Translated by ChatGPT 5