题目描述

如果一个序列满足下面的性质，我们就将它称为摆动序列：

• $\red{1}$. 序列中的所有数都是不大于k的正整数；
• $\red{2}$. 序列中至少有两个数。
• $\red{3}$. 序列中的数两两不相等；
• $\red{4}$. 如果第$\red{i – 1}$个数比第$\red{i – 2}$个数大，则第$\red{i}$个数比第$\red{i – 2}$个数小；如果第$\red{i – 1}$个数比第$\red{i – 2}$个数小，则第$\red{i}$个数比第$\red{i – 2}$个数大。 比如，当$\red{k = 3}$时，有下面几个这样的序列： $\red 1$ $\red 2$ $\red 1$ $\red 3$ $\red 2$ $\red 1$ $\red 2$ $\red 1$ $\red 3$ $\red 2$ $\red 3$ $\red 2$ $\red 3$ $\red 1$ $\red 3$ $\red 1$ $\red 3$ $\red 2$ 一共有$\red{8}$种，给定 $\red{k}$ ，请求出满足上面要求的序列的个数。

输入格式

输入包含了一个整数 $\red{k}$ 。$\red{（ k <=20）}$

输出格式

输出一个整数，表示满足要求的序列个数。

样例

输入样例

3

输出样例

8