问题描述

泰波那契序列 $T_n$ 定义如下：

$T_0 = 0, T_1 = 1, T_2 = 1$, 且在 $n \geq 0$ 的条件下 $T_{n+3} = T_n + T_{n+1} + T_{n+2}$。

给你整数 $n$，请输出第 $n$ 个泰波那契数 $T_n$ 的值。

格式

输入

一个整数 $n$。

输出

一个整数，即 $T_n$。

样例

4

4

25

1389537

提示

样例说明

样例一：$T_3 = 0 + 1 + 1 = 2$、$T_4 = 1 + 1 + 2 = 4$

数据范围

• $0 \leq n \leq 37$
• 答案保证是一个 $32$ 位整数，即 $\leq 2^{31} - 1$。