邮政货车

题号：NC22996
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld

题目描述

郊区呈矩形，有四条东西方向的街道和N（1<=N<=1000）条南北方向的街道。在郊区的西北角有一个邮局。

如N=5时，郊区如下图所示，圆点表示邮局，直线表示街道。

每天邮政卡车从邮局出发，每个十字路口（包括边界和四角）经过且只经过一次。现在邮局希望知道邮政货车行驶的路线有几种。例如，下面两幅图表示的是满足上图的两条路线

另一个例子，下面四幅图表示了当N=3时的全部四种情况

一行：一个数值N

到INPUT中给出的街道的路径总数

示例1

复制

复制