Description

Ningning considers the following problem: given an operand sequence $1, 2, \ldots, n$ (the figure illustrates the case for $1$ to $3$), stack A has depth greater than $n$.

Two operations are allowed:

1. Move a number from the head of the operand sequence to the top of the stack (corresponding to the stack push operation).
2. Move a number from the top of the stack to the end of the output sequence (corresponding to the stack pop operation).

Using these two operations, one operand sequence can produce a set of output sequences. The following figure shows the process of generating the sequence 2 3 1 from 1 2 3.

(The initial state is as shown above.)

For a given $n$, your program should compute and output the total number of output sequences that can be obtained from the operand sequence $1, 2, \ldots, n$ through these operations.

Input Format

The input contains a single integer $n$ ($1 \leq n \leq 18$).

Output Format

Output a single line containing the total number of possible output sequences.

3

5

Hint

Source: NOIP 2003 Junior, Problem 3.

Translated by ChatGPT 5