В начале координат бесконечной двумерной плоскости находится робот. Каждую секунду робот перещается ровно на \(1\) метр в одном из четырёх направлений: на север, юг, запад или восток. Робот может выбрать произвольное направление для первого шага, но после этого в конце каждой секунды он обязан повернуть на 90 градусов влево или вправо относительно направления, в котором только что двигался. Например, если робот только что переместился на север или юг, его следующий шаг должен быть на запад или восток, и наоборот.
Робот совершает ровно \(n\) шагов из начального положения в соответствиями с правилами выше. В скольких различных точках робот может оказаться в итоге? Финальное направление робота можно игнорировать.
Выходные данные
Выведите одно целое число — количество различных возможных положений робота после ровно \(n\) шагов.
Примечание
В первом примере робот переместится на 1 метр на север, юг, запад или восток в зависимости от исходного направления.
Во втором примере робот всегда окажется в \(\sqrt{2}\) метрах на северо-западе, северо-востоке, юго-западе или юго-востоке.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
|
4
|
|
2
|
2
|
4
|
|
3
|
3
|
12
|