Description

 我们来玩一个游戏：自然数1到N，按顺序列成一排，你可以从中取走任意个数，但是相邻的两个不可以同时被取走。如果你能算出一共有多少种取法，那么你会被天神Lijiganjun奖励。

Input Format

  仅包含一个数n（1< n < 50）。

Output Format

 仅包含一个数———你的答案。

5

13

Hint

n=45 的时候，已经超过1亿，用long long int 定义

Source

递推递归