中位数

题号：NC295401
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 给定一个整数 $n$ ，现在对于一个长度为 $n$ 的排列 $p_1,p_2,\dots,p_n$ ，其价值 $\operatorname{v}(p)$ 定义为：

$\operatorname{v}(p)=\textstyle\prod\limits_{l=1}^{n}\textstyle\prod\limits_{r=l}^{n}\operatorname{mid}(l,r)$

$\hspace{15pt}$ 现在，需要你求出所有 $n!$ 种不同排列的价值的总乘积。由于答案可能很大，请将答案对 $1\,610\,612\,741$ （TXT文本复制：1610612741）取模后输出。

【名词解释】
$\hspace{15pt}$ $\operatorname{mid}(l,r)$ 指的是区间 $[l,r]$ 内第 $\left \lceil \tfrac{r-l+1}{2} \right \rceil$ 大的数值，例如：数组 $\{1,2,3,4\}$ 中第 $1$ 大是 $4$ ，第 $2$ 大是 $3$ ，第 $3$ 大是 $2$ ，第四大是 $1$ ，所以，这个数组的中位数是第 $2$ 大的数，是 $3$ 。
$\hspace{15pt}$ 长度为 $n$ 的排列是由 $1,2,\dots,n$ 这 $n$ 个整数、按任意顺序组成的数组（每个整数均恰好出现一次）。例如， $\{2,3,1,5,4\}$ 是一个长度为 $5$ 的排列，而 $\{1,2,2\}$ 和 $\{1,3,4\}$ 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。

输入描述:

第一行输入一个整数  ，表示排列  的长度。

输出描述:

输出一个整数，代表所有  种不同排列的价值的总乘积。由于答案可能很大，请将答案对  取模后输出。

示例1

输入

复制

输出

复制

说明

在这个样例中，一共有  种不同排列： 
对于排列 ，则对应的 ； 
对于排列 ，则对应的 。
则最后总价值的乘积为 。

示例2

输入

复制

输出

复制

1294676896