Nth Tribonacci Number

Statement

Tribonacci numbers are a sequence of numbers where each number is the sum of the three preceding numbers. Your task is to find the $n^{th}$ Tribonacci number.

The Tribonacci sequence is defined as:

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

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

Let’s say you have to find the fifth Tribonacci number in the sequence. From the sequence defined above, we know that $T_0 = 0, T_1 = 1, T_2 = 1$. The sequence will be:

$0, 1, 1, 2, 4, 7$

Therefore, the fifth term will be 7.

Constraints:

• $0 \leq$ n $\leq 73$
• The answer is guaranteed to fit within a 64-bit integer, i.e., answer $\leq 2 ^{63} - 1$

Examples