C. Вызовы с запоминанием

Ту же рекурсию для чисел Трибоначчи снабдили запоминанием: перед вычислением функция смотрит, не считалось ли это значение раньше, и если считалось — сразу возвращает готовое, ничего больше не вызывая.

Посчитайте, сколько всего вызовов функции произойдёт при вычислении $T_n$, включая самый первый и включая те вызовы, которые сразу вернули готовое значение.

Сравните с классной задачей: там число вызовов росло экспоненциально, здесь — линейно. Разница видна уже на третьем десятке.

Одна строка содержит число $n$ ($1 \le n \le 10^6$).

Одно число — количество вызовов.