题目描述

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

$\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）}$

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