A83228.神奇的数列

小码君最近发现了一个神奇的数列，数列的第一项等于 $1$，即 $a_1=1$。后面的数由以下规则生成，对于第 $i$ 项：

1. 如果 $i$ 是偶数，则 $a_i=2 * a_{i-1}$。
2. 否则，$a_i=a_{i-1}+a_{i-2}$。

你需要告诉小码君数列的第 $n$ 项的值是多少。

一行一个整数 $n(1 \leq n \leq 20)$，表示要求出数列的第 $n$ 项。

输出数列的第 $n$ 项的值。

对于 $50\%$ 的数据 $1 \leq n \leq 10$。

对于 $100\%$ 的数据 $1 \leq n \leq 20$。

样例 1 解释：

第 1 项为 1

第 2 项为第 1 项的 2 倍，即第 2 项为 2

第 3 项为第 2 项加第 1 项，即第 3 项为 3