题目背景

小w 有 $n$ 个电量 分别为 $1, 2, \dots, n$ 的充电宝。他发现如果相邻两个充电宝的电量乘积为偶数，它们之间就能产生稳定的能量场。小明想知道，将这 $n$ 个充电宝排成一排，有多少种排列方式能让每一对相邻的充电宝都产生稳定的能量？

$n$ 的全排列是指将 $1, 2, \dots, n$ 这 $n$ 个数字不重复地排成长度为 $n$ 的序列。

题目描述

给定一个正整数 $n$，定义“良好的排列”为：在该排列中，任意相邻两个数的乘积均为偶数。求 $1$ 到 $n$ 的所有全排列中，有多少个是良好的排列。

输入格式

一个整数 $n$，满足 $2 \leq n \leq 12$。

输出格式

一个整数，表示良好的排列的总数。

样例

3

2

样例解释

当 $n = 3$ 时，所有全排列为：

$(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)$

• $(1,2,3)$：乘积为 $1 \times 2 = 2$（偶数），$2 \times 3 = 6$（偶数），符合。
• $(3,2,1)$：乘积为 $3 \times 2 = 6$（偶数），$2 \times 1 = 2$（偶数），符合。

共有 2 个良好的排列。