一个正方形的镇区分为 $N∗N(1≤N≤7)$ 个小方块。农场位于方格的左上角，集市位于左下角。

Betsy 穿过小镇，从左上角走到左下角，刚好经过每个方格一次。

当 $N=3$ 时，Betsy 的漫游路径可能如下图所示：

请你帮忙计算 Betsy 有多少种不同的旅行方案。

请勿使用打表此类的行为完成本题，否则一律取消成绩

输入格式

输入一行一个整数 $(1≤N≤7)$。

输出格式

输出一行表示不同的路径数。

格式说明输出时每行末尾的多余空格，不影响答案正确性

输入、输出要求要求使用「文件输入、输出」的方式解题，输入文件为 Betsy.in，输出文件为 Betsy.out

样例输入

3

样例输出

2