题目描述

蓝桥学院由 $N$ 栋教学楼组成，教学楼编号 $1$ 到 $N$。对于两栋教学楼 $a$ 和 $b$，当 $a$ 和 $b$ 互质时，$a$ 和 $b$ 之间有一条走廊直接相连，两个方向皆可通行，否则没有直接连接的走廊。

小蓝现在在第一栋教学楼，他想要访问每栋教学楼正好一次，最终回到第一栋教学楼（即走一条哈密尔顿回路)，请问他有多少种不同的访问方案？两个访问方案不同是指：存在某个 $i$ ，小蓝在两个访问方案中访问完教学楼 $i$ 后访问了不同的教学楼。

输入描述

只有一个整数 $N$。

输出描述

对每个输入输出一个整数表示答案。

3

2

1231,1321

6

4

1234561,1432561,1652341,1654321.

评测用例规模与约定：

对于所有评测用例，$1≤N≤21$。