巡检步数

题目描述

巡检机器人在无限大的方格网中行走，规则如下：

1. 每一步只能移动到相邻方格（北、东、西三个方向，不能向南）；
2. 走过的方格立即塌陷，不能再走第二次。

从原点出发走 $n$ 步，共有多少种不同的行走方案（只要某一步的方向不同即为不同方案）？

输入格式

一行，一个整数 $n$（$n \le 20$）。

输出格式

一行，一个整数：方案总数。

数据范围