小红的好排列_牛客题霸

小红认为一个偶数长度为的排列是好排列，当且仅当恰好有一半的使得是的倍数。小红想知道，全部长度为的排列中，共有多少个好排列？由于答案可能很大，请将答案对取模后输出。长度为的排列是由这个整数、按任意顺序组成的数组，其中每个整数恰好出现一次。例如，是一个长度为的排列，而和都不是排列，因为前者存在重复元素，后者包含了超出范围的数。

输入描述:

在一行上输入一个正偶数 代表排列中的元素数量。

输出描述:

输出一个整数，代表好排列的数量。由于答案可能很大，请将答案对 取模后输出。

示例1

输入

输出

说明

在这个样例中，长度为  的排列有且仅有两个：
，第一个元素  使得 ，第二个元素  使得 ，均不是  的倍数；
，同理。
因此，长度为  的排列中，不存在好排列。

示例2

输入

输出

说明

在这个样例中，一共有  个长度为  的排列满足条件，例如：
，第一个元素  使得 ，第二个元素  使得 ，第三个元素  使得 ，第四个元素  使得 ，恰好有一半的  使得  是  的倍数。