Баба Яга поймала Ивана Царевича и загадала ему загадку. Решит — освободится. Не решит — с голоду помрёт.

На клетчатой сетке нарисован многоугольник. Требуется соединить зелёный кружок с красным квадратиком.

Есть ограничения:

• линии можно проводить только в четырёх возможных направлениях (показаны на картинке ниже)
• нельзя касаться границы многоугольника

Возможные направления:

Но Баба Яга не была бы Бабой Ягой, если бы задача была такой простой. Ивану Царевичу нужно не соединить кружок с квадратиком, а вычислить количество всевозможных способов их соединения.

Сколько способов соединить кружок с квадратиком?