1128. N-th Tribonacci — Space Optimized

Compute the nth Tribonacci number where T(0)=0, T(1)=1, T(2)=1, and T(n)=T(n-1)+T(n-2)+T(n-3), using only constant extra space. The input is JSON {n}.

Input: JSON {n}.

Output: Integer — the nth Tribonacci number.

Examples

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

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

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

Constraints

• 0<=n<=37

Asked by