PAROVI

Mirko and Slavko play a game. Mirko moves first: he picks a non-empty set of pairs of integers between $1$ and $N$, where the two numbers of a pair are different and coprime. For $N = 5$, one possible choice is $\{\{1, 2\}, \{3, 4\}, \{2, 5\}, \{3, 5\}\}$.

Slavko moves second, and he looks for a split point of Mirko's set. Mirko's set has a split point if there is an integer $x$ in $\{2, 3, \ldots, N\}$ such that every pair $\{a, b\}$ of the set satisfies one of the following:

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

For example, the set $\{\{1, 2\}, \{3, 4\}\}$ has the split point $x = 3$. Whenever a split point exists, Slavko finds it.

Mirko wins when Slavko finds no split point. Count how many different sets of pairs Mirko can pick and be sure of winning. The count can be very large, so print it modulo $1\,000\,000\,000$.

The first line contains the integer $N$ ($1 \le N \le 20$).

Print the required count on the first and only line.

For $N = 2$ the only set that meets the requirement is $\{\{1, 2\}\}$.

For $N = 3$, one set that meets the requirement is $\{\{1, 3\}, \{1, 2\}\}$.