747. Tribonacci Number

The Tribonacci sequence T(n) is defined as:

``
T(0) = 0, T(1) = 1, T(2) = 1
T(n) = T(n-1) + T(n-2) + T(n-3) for n >= 3
``

Given an integer n, return the value of T(n). Each term is the sum of the three preceding terms.

Input: A single non-negative integer n (0 <= n <= 37).

Output: A single integer — the n-th Tribonacci number.

Examples

Input: 4
Output: 4
Explanation: T(3)=0+1+1=2, T(4)=1+1+2=4.

Input: 0
Output: 0
Explanation: Base case T(0)=0.

Input: 25
Output: 1389537
Explanation: T(25) = 1389537.

Constraints

• 0 <= n <= 37

Asked by