XO Problem

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

一天 X 给 O 出了一道题:用 X 和 O 两个字符来组成长度为 n 的字符串一共有多少种方法呢?这里有一个限制条件,当出现 O 的时候必须是 2 个一起才可以。比如:XOX、OOO、XOOO 是不可以的,而 XOOX、OOX、XOO 是可以的。

Input

多组输入。

每组一个整数 n (1 <= n <= 100)。

Output

一个整数,表示题目中所询问的用 X 和 O 两个字符来组成长度为 n 的字符串一共有多少种方法(当出现 O 的时候必须是 2 个一起才可以)。

Sample Input

1
3
100

Sample Output

1
3
35734758952996318

Hint

Source

【2016级《程序设计基础(B)II》期末上机考试-补测】UMR