P7800 [COCI 2015/2016 #6] PAROVI

$\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$.

The first line contains an integer $N$.

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

**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](https://hsin.hr/coci/archive/2015_2016/) [CONTEST #6](https://hsin.hr/coci/archive/2015_2016/contest6_tasks.pdf) T4 PAROVI**. **This problem uses the original COCI scoring, with full score $120$**. Translated by ChatGPT 5