Problem C: 骨牌铺法2

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：87 Solved：45

Description

    在2×n的长方形方格中，用n个1×2的骨牌铺满方格。骨牌可竖铺也可以横铺，若输入n后，求铺放满2×n方案的总数？     例如：n=3时，有2×3方格，骨牌的铺放方案有三种方法，如下图所示：
 


Input

输入一个正整数 n。( 1<=n<=80) 

Output

 输出一个正整数为铺放满2×n方案的总数。

Sample Input Copy 

3

Sample Output Copy 

3

HINT

1<=n<=80
 输出数据较大，请用递推算法并使用long long长整型。