Betsy 的旅行

Don Piele

一个正方形城镇被划分成 N² 个正方形地块（1 ≤ N ≤ 7）。农场位于左上角地块，市场位于左下角地块。Betsy 从农场出发，步行穿过每个地块恰好一次，最后到达市场。下图是 N=3 时 Betsy 可能的一条路线。

----------------
|    |    |    |
| F**********  |
|    |    | *  |
------------*---
|    |    | *  |
|  *****  | *  |
|  * | *  | *  |
---*---*----*---
|  * | *  | *  |
|  M | ******  |
|    |    |    |
----------------

编写一个程序，对于给定的 N，计算 Betsy 从农场到市场可以走的不同路线的数量。

程序名称：betsy

输入格式

第 1 行：一个整数 N（1 ≤ N ≤ 7）

样例输入（文件 betsy.in）

3

输出格式

一行一个整数，表示不同路线的数量。

样例输出（文件 betsy.out）

2