12845: 【创新型23361】第7章:函数 第39级台阶

Memory Limit:4 MB Time Limit:3.000 S
Judge Style:Text Compare Creator:
Submit:2 Solved:0

Description


小明刚刚看完电影《第39级台阶》,离开电影院的时候,他数了数礼堂前的台阶数,恰好是39!  站在台阶前,他突然又想着一个问题: 如果我每一步只能迈上1个或2个台阶。先迈左脚,然后左右交替,最后一步是迈右脚,也就是说一共要走偶数步。那么,上完39级台阶,有多少种不同的上法呢?从键盘输入给定一个nn<=39),表示几阶台阶,编程计算并输出种类的数目。


Input

1个数nn<=39),表示几阶台阶。

Output

51167078

Sample Input Copy

39

Sample Output Copy

51167078