#NC205036. 答题卡
答题卡
题目描述
牛牛即将要参加考试,他学会了填答题卡。
可惜他竖着的答题卡填成了横着的 : (

好奇的他想知道对于 道题,每道题 个选项的答题卡( 的矩阵),满足横答题卡和竖答题卡图形一致的方案数有多少种。
注:每道题只能选择一个选项,即每行恰好涂黑一个格子,整个矩阵中恰好涂黑 个格子。横竖对称指矩阵关于主对角线对称。
当 时,四种符合要求的方案如下:

输入格式
第一行给出整数 ,。
输出格式
输出方案数,答案对 取模。
样例 1
3
4
牛牛即将要参加考试,他学会了填答题卡。
可惜他竖着的答题卡填成了横着的 : (

好奇的他想知道对于 n 道题,每道题 n 个选项的答题卡(n×n 的矩阵),满足横答题卡和竖答题卡图形一致的方案数有多少种。
注:每道题只能选择一个选项,即每行恰好涂黑一个格子,整个矩阵中恰好涂黑 n 个格子。横竖对称指矩阵关于主对角线对称。
当 n=3 时,四种符合要求的方案如下:

第一行给出整数 n,1≤n≤105。
输出方案数,答案对 109+7 取模。
3
4