题目描述

有一个由多个小正六边形组成的蜂巢图案，蜂巢外缘各边的小正六边形数量一致，且左右对称。

以下为竖直对称线上小正六边形个数为3、5、7的3个蜂巢图案。

编程实现： 有一只蜗牛要从竖直对称线顶端的小正六边形处移动到底端的小正六边形中， 它每次只能向它所在位置的小正六边形的左下方、正下方、右下方相邻的小正六边形处移动。

已知竖直对称线上有N个小正六边形，请计算出蜗牛从竖直对称线顶端移动到底端共有多少条不同的移动路线。 例如：N = 3，竖直对称线上有3个小正六边形，如下图：

蜗牛从竖直对称线顶端的小正六边形处（1号处）移动到另一端的小正六边形中（7号处）共有11条不同的路线。

11条不同的路线分别为：

（1->2->5->7）、（1->2->4->7）、（1->2->4->5->7）、（1->2->4->6->7）、
（1->4->5->7）、（1->4->7）、（1->4->6->7）、（1->3->4->5->7）、（1->3->4->7）、
（1->3->4->6->7）、（1->3->6->7）。

输入格式

输入一个正整数N（2＜N＜30，N为奇数），表示图案上竖直对称线上小正六边形的个数

输出格式

输出一个整数，表示蜗牛从竖直对称线顶端移动到底端共有多少条不同的移动路线

3

11