恶魔和天使在玩一个游戏：自然数1到N，按顺序列成一排，可以从中取走任意个数(可以一个也不取)，但是相邻的两个不可以同时被取走。
如果你能算出一共有多少种取法，那么恶魔将会改邪归正，否则天使将会被惩罚。

输入一行，一个正整数n（1< n < = 50）。

输出一行，仅包含一个正数即你的答案。

递推 level2