题目描述

泰波那契数列-递推法 泰波那契数列的前三项分别是1、1、2，从第四项开始，每一项都是前三项的和，即：T(n) = T(n-1) + T(n-2) + T(n-3)。 输入n，输出泰波那契数列第n项。

输入格式

一个整数n（4 ≤ n ≤ 30）。

输出格式

泰波那契数列第n项的值。

样例

输入样例 1

20

输出样例 1

66012

输入样例 2

1

输出样例 2

1

输入样例 3

5

输出样例 3

7