Tribonacci Sequence

You are given a non-negative integer n. Your task is to compute the n-th Tribonacci number where the Tribonacci sequence is defined by the recurrence relation:

\(T(0)=0, \quad T(1)=1, \quad T(2)=1, \quad \text{and} \quad T(n)=T(n-1)+T(n-2)+T(n-3)\) for all \(n \geq 3\).

For example, the beginning of the sequence is: 0, 1, 1, 2, 4, 7, ...

Read the input from standard input and output the result to standard output.

inputFormat

The input consists of a single line containing a non-negative integer n (0 ≤ n ≤ 10⁵).

outputFormat

Output a single number, the n-th Tribonacci number.

0

0