Последовательность чисел Трибоначчи (Tn) определяется следующим образом:
T0 = 0,
T1 = 1,
T2 = 1, и Tn+3 = Tn + Tn+1 + Tn+2 при n >= 0.
Для заданного числа n, определите значение Tn.
Входные данные
Программа получает на вход натуральное число n (0 <= n <= 37). Ответ гарантированно укладывается в рамки 32-разрядного целого числа, т.е. ответ <= 2
31 - 1.
Выходные данные
Выведите значение T
n.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
4 |
4 |
| 2 |
25 |
1389537 |
Запрещенные операторы: for; while