Nth Tribonacci Number

Statement

Given a number $n$, calculate the corresponding Tribonacci number. The Tribonacci sequence $T_n$ is defined as:

$T_0 = 0,\space T_1 = 1,\space T_2 = 1$, and $\space T_{n+3} = T_n + T_{n+1} + T_{n+2},\space$ for $n >= 0$

Constraints

The input number, $n$, is a non-negative integer.

Example

Sample input

4

Expected output

4

Try it yourself