#NC205036. 答题卡

答题卡

题目描述

牛牛即将要参加考试,他学会了填答题卡。

可惜他竖着的答题卡填成了横着的 : (

横竖答题卡示意图

好奇的他想知道对于 nn 道题,每道题 nn 个选项的答题卡(n×nn\times n 的矩阵),满足横答题卡和竖答题卡图形一致的方案数有多少种。

注:每道题只能选择一个选项,即每行恰好涂黑一个格子,整个矩阵中恰好涂黑 nn 个格子。横竖对称指矩阵关于主对角线对称。

当 n=3n=3 时,四种符合要求的方案如下:

n为3的四种合法方案

输入格式

第一行给出整数 nn,1≤n≤1051\le n\le 10^5。

输出格式

输出方案数,答案对 109+710^9+7 取模。

样例 1

3
4

来源

牛客原题