题目描述

从1到n这n个数中任取出若干数，不能取相邻的数，并且至少取1个。

输入一个数n，计算共有多少种不同的取法。

例如：n=3时，共有4种不同的取法：{1}，{2}，{3}，{1,3}。

输入格式

一个整数n(1≤n≤20)。

输出格式

一个整数，为取数的方法数。

输入/输出样例

3

4

12

376

说明/提示

时间1000ms，内存256MiB