1450: 蜂巢路线

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

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

现在有一只蜗牛要从竖直对称线顶端的小正六边形处移动到底端的小正六边形中，每次只能向左下方、正下方、右下方的小正六边形进行移动。

当N = 3时，如下图：

共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（N为奇数），表示图案上竖直对称线上小正六边形的个数。

输出一个整数，代表有多少种移动路线。

3

11