Nth Tribonacci Number

Given a number n, calculate the corresponding Tribonacci number.

Statement

Given a number nn, calculate the corresponding Tribonacci number. The Tribonacci sequence TnT_n is defined as:

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

Constraints

The input number, nn, is a non-negative integer.

Example

Sample input

4

Expected output

4

Try it yourself

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.