题目描述

任何一门数据结构的课程都会介绍栈。宁宁同学在复习栈的基本概念时，想到了一个书上没有讲过的问题，而他自己无法给出答案，所以需要你的帮忙。

宁宁考虑的是这样一个问题：一个操作数序列，从$\red {1，2}$，一直到$\red {n}$(图示为$\red {1}$到$\red {3}$的情况)，栈$\red {A}$的深度大于$\red {n}$。

现在可以进行两种操作，

1.将一个数，从操作数序列的头端移到栈的头端(对应数据结构栈的$\red {push}$操作)

2. 将一个数，从栈的头端移到输出序列的尾端（对应数据结构栈的$\red {pop}$操作）

使用这两种操作，由一个操作数序列就可以得到一系列的输出序列，下图所示为由$\red {1 2 3}$生成序列$\red {2 3 1}$的过程。（原始状态如上图所示）

你的程序将对给定的$\red {n}$，计算并输出由操作数序列$\red {1，2，…，n}$经过操作可能得到的输出序列的总数。

输入格式

只含一个整数$\red {n（1≤n≤18）}$

输出格式

只有一行，即可能输出序列的总数目

样例

输入样例

3

输出样例

5