PAROVI

미르코와 슬라브코가 게임을 한다. 미르코가 먼저 $1$ 이상 $N$ 이하의 정수 두 개로 이루어진 쌍을 모아 비어 있지 않은 집합을 하나 고른다. 한 쌍을 이루는 두 수는 서로 다르고 서로소여야 한다. 예를 들어 $N = 5$이면 미르코는 $\{\{1, 2\}, \{3, 4\}, \{2, 5\}, \{3, 5\}\}$를 고를 수 있다.

다음은 슬라브코 차례다. 슬라브코는 미르코가 고른 집합의 분할점을 찾는다. 집합에 속한 모든 쌍 $\{a, b\}$에 대해 다음 중 하나가 성립하는 정수 $x$가 $\{2, 3, \ldots, N\}$ 안에 있으면, 그 집합에는 분할점이 있다.

• $a < x$이고 $b < x$
• $a \ge x$이고 $b \ge x$

예를 들어 집합 $\{\{1, 2\}, \{3, 4\}\}$는 $x = 3$이 분할점이다. 분할점이 있으면 슬라브코는 반드시 찾아낸다.

슬라브코가 분할점을 찾지 못하면 미르코가 이긴다. 미르코가 처음에 골라서 확실히 이기는 집합이 몇 개인지 구하라. 개수가 매우 클 수 있으므로 $1\,000\,000\,000$으로 나눈 나머지를 출력한다.

첫째 줄에 정수 $N$ ($1 \le N \le 20$)이 주어진다.

첫째 줄에 구한 개수를 출력한다.

$N = 2$일 때 조건을 만족하는 집합은 $\{\{1, 2\}\}$ 하나뿐이다.

$N = 3$일 때 조건을 만족하는 집합의 예로 $\{\{1, 3\}, \{1, 2\}\}$가 있다.