U646319 非攻

> 有利于人的，就是巧，就是好，不利于人的，就是拙，也就是坏的｡

｢你一行义，可把我的饭碗打碎了！今后就只好做些玩具……｣公输般的云梯在墨子的战法面前败下阵来，不甘心的他掏出一副纸牌，｢这是我发明的纸牌，一共有 $n$ 张，分别写有数字 $1 \sim n$，咱们来玩个游戏。｣ 他洗了洗牌，抹匀在墨子面前。 ｢每次只能交换两张牌，交换的代价是这两张牌上的数字之积，请先生用**最少的交换次数**帮我把这副牌排回升序。看看您花费的总代价是多少。｣ 墨子笑了笑，很快就将牌排好序，花费的总代价还是所有方案中最小的。公输般刚要称赞，墨子又说出了将所有 $ n! $ 种初始排列用最少的交换次数后排好序所花费的最小总代价之和。这让他大惊失色，所以来请教学 OI 的你墨子是如何做到的。

一个正整数 $n$。

一个整数，代表将所有长度为 $n$ 的排列用最少交换次数后排好序的最小总代价之和。 答案对 $10^{9}+7$ 取模｡

### 样例 1 解释 长度为 $3$ 的排列有 $6$ 个，将它们排好序的最优方案如下： $(1,2,3)$ 交换 $0$ 次，代价为 $0$； $(1,3,2)$ 交换 $1$ 次，代价为 $6$； $(2,1,3)$ 交换 $1$ 次，代价为 $2$； $(2,3,1)$ 交换 $2$ 次，代价为 $5$； $(3,1,2)$ 交换 $2$ 次，代价为 $5$； $(3,2,1)$ 交换 $1$ 次，代价为 $3$； 所有排列的代价之和为 $21$。 ### 数据范围 ::cute-table{tuack} |测试点编号 |$n \le$ | |:--------:|:------:| |$1\sim 2$ |$10$ | |$3\sim 6$ |$100$ | |$7\sim 10$|$2000$ | |$11\sim 20$|$10^{7}$| ['](https://www.luogu.me/article/8ujnzsn2)