题面：相邻不连续的排列

时间限制： 1 秒 内存限制： 256 MB

给定一个整数 n。

你需要把 1, 2, ..., n 这 n 个数排成一行，每个数恰好出现一次。

如果排列中任意两个相邻位置上的数，它们的差的绝对值都不等于 1，那么这个排列就是合法的。

请你计算一共有多少个合法排列。

输入格式

输入一行，包含一个整数 n。

输出格式

输出一个整数，表示合法排列的数量。

数据范围

1 <= n <= 10

样例

输入

4

输出

2

说明

当 n = 4 时，合法排列有：

2 4 1 3
3 1 4 2

所以答案为 2。

测试点说明表