有一天,$$$n$$$人($$$n$$$为偶数)在广场上相遇,跳了两场圆舞,每场圆舞恰好由$$$\frac{n}{2}$$$人组成。你的任务是找出 $$$n$$$ 人跳两段圆舞的方法数,如果每个圆舞正好由 $$$\frac{n}{2}$$$ 人组成。每个人都应该属于这两种圆舞中的一种。
圆舞是由$$$1$$$或更多人组成的舞蹈圈。如果可以通过选择第一个参与者将一个圆舞转变为另一个圆舞,则两个圆舞是无法区分的(相等)。例如,圆舞 $$$[1, 3, 4, 2]$$$、$$$[4, 2, 1, 3]$$$ 和 $$$[2, 1, 3, 4]$$$ 是无法区分的。
例如,如果$$$n=2$$$,则方式数为$$$1$$$:一轮圆舞由第一人组成,第二人为第二人。
例如,如果$$$n=4$$$,则路数为$$$3$$$。可能的选项:
- 一轮舞蹈 — $$$[1,2]$$$,另一场 — $$$[3,4]$$$;
- 一轮舞蹈 — $$$[2,4]$$$,另一场 — $$$[3,1]$$$;
- 一轮舞蹈 — $$$[4,1]$$$,另一场 — $$$[3,2]$$$。
如果每个圆舞恰好由 $$$\frac{n}{2}$$$ 人组成,那么您的任务是找出 $$$n$$$ 人可以跳两段圆舞的方式数量。
输入
输入包含一个整数$$$n$$$ ($$$2 \le n \le 20$$$),$$$n$$$ 为偶数。
输出
打印一个整数——跳两圈圆舞的方式数。保证答案符合 $$$64$$$ 位整数数据类型。
示例
输入 #1
2
输出 #1
1
输入 #2
4
输出 #2
3
输入 #3
8
输出 #3
1260
输入#4
20
输出#4
12164510040883200