说明

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

1. 序列中的所有数都是不大于$k$的正整数；

2. 序列中至少有两个数。

3. 序列中的数两两不相等；

4. 如果第$i$ – 1个数比第$i$ – 2个数大，则第$i$个数比第$i$ – 2个数小；如果第$i$ – 1个数比第$i$ – 2个数小，则第$i$个数比第$i$ – 2个数大。

比如，当$k$ = 3时，有下面几个这样的序列：

1 2
1 3
2 1
2 1 3
2 3
2 3 1
3 1
3 2

一共有8种，给定$k$，请求出满足上面要求的序列的个数

输入格式

输入包含了一个整数$k$。（$k\leqslant 20$）

输出格式

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

样例

3

8

来源

蓝桥杯算法训练