一天，wzn研究所的工作人员发现在wzn药水中发现了一串神秘的基因序列，将他命名为wzn数列

wzn数列前几项如下： 1 1 2 3 5 8 13...... 这个基因数列的第n项有着巨大的秘密，请你帮他们找到第n项的数

输入格式
第一行：一个数 n

输出格式
一行：一个数，数列的第n项

输入输出样例
输入
5
输出
5
输入
6
输出
8
说明/提示
n<=50 要求用递归来做，不能记忆化（禁用数组）