求C题分析过程
链接：https://ac.nowcoder.com/acm/contest/5389/C
来源：牛客网
来源：牛客网
题目描述
牛牛即将要参加考试，他学会了填答题卡。
可惜他竖着的答题卡填成了横着的 : (
可惜他竖着的答题卡填成了横着的 : (
好奇的他想知道对于 n 道题，每道题 n 个选项的答题卡 ( n * n 的矩阵 )，满足横答题卡和竖答题卡图形一致的方案数有多少种。
注：每道题只能选择一个选项，即 n * n 的矩阵中只能涂黑 n 个空。求横竖对称的方案数。
输入描述:
第一行给出 n。
输出描述:
输出方案数，答案对 109+710^9+7109+7 取模 示例1
输入
3
输出
4
说明
备注:
对于 50%50\;\%50% 的数据有 n≤10n \leq 10n≤10 对于 100%100\;\%100% 的数据有 n≤105n\le 10^5n≤105
