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