Вычислите, сколько существует различных путей для путешествия «хромого» короля из левого нижнего угла доски размером NxN в правый верхний угол, при котором король не проходит дважды по одной и той же клетке. «Хромой» король в отличие от обычного короля в шахматах не может выполнять ход по диагонали вниз-влево (см. рисунок).
Пути считаются различными, если они проходят по различным клеткам или обходят клетки в разном порядке. Например, для доски 2x2 существует 5 различных путей: a1-b2, a1-a2-b2, a1-b1-b2, a1-a2-b1-b2, a1-b1-a2-b2.
Вычислите ответ для N=4.