Плесень

Ремейк задачи Всероссийской командной олимпиады школьников по програмированию

Как известно, плесени свойственно разрастаться. По каким правилам? Чтобы это выяснить, учёные поместили колонию плесневых грибков на одну клеточку вафли и стали наблюдать. На второй день плесень заполнила все клетки, соприкасающиеся с заплесневелой стороной или углом. На третий день плесень поразила те клетки, которые имели общую сторону с заплесневелыми, на четвёртый - опять плесень опять распространялась на другие клетки и через общую сторону, и через угол. В итоге учёные сделали вывод, что плесень в нечётные дни распространяется только через общую сторону, а в нечётные ещё и через общий угол.

Непонятно? Вот картинка, на которой колония плесени на 5-й день эксперимента. Число обозначает день, на который клетка заплесневела. Как видите, после 5 дней плесень занимает 69 клеток вафли.

Разработайте программу, которая определяет количество клеток, занятых плесенью за первые N дней эксперимента.

Входные данные. Натуральное число N, не превышающее 100 миллионов - продолжительность эксперимента.

Выходные данные. Одно натуральное число - количество клеток, занятых плесенью после N дней эксперимента.