Description

There are many variants of rotaviruses. Many rotaviruses are generated from a wheel base. An $n$-wheel base consists of $n$ distinct base atoms on a circular ring and one core atom at the center. An edge between $2$ atoms represents the information channel between these $2$ atoms, as shown in Figure 1.

The generation rule of an $n$-rotavirus is to delete some edges in the $n$-wheel base so that there is a unique information path between any two atoms. For example, there are $16$ different $3$-rotaviruses, as shown in Figure 2.

Given $n\ (n \le 100)$, write a program to compute how many different $n$-rotaviruses there are.

Input Format

The first line contains $1$ positive integer $n$.

Output Format

Output $1$ line, the number of different $n$-rotaviruses.

3

16

Hint

Translated by ChatGPT 5