1118. Tribonacci Number

The Tribonacci sequence is defined by T(0)=0, T(1)=1, T(2)=1, and T(n)=T(n-1)+T(n-2)+T(n-3) for n>=3. Given n, return T(n). The input is JSON {n}.

Input: JSON {n}.

Output: Integer — the nth Tribonacci number.

Examples

Example 1

Input: {"n":4}
Output: 4
Explanation: 0,1,1,2,4.

Example 2

Input: {"n":0}
Output: 0
Explanation: Base case.

Example 3

Input: {"n":25}
Output: 1389537
Explanation: T(25) = 1389537.