package main import . "fmt" import . "math/big" var mint = newMint(1e9+7) func main() { var n int Scan(&n) ans := mint.Div(mint.Mul(mint.Sub(mint.Mul(mint.Nsum(n-1), n), mint.N2sum(n-1)), 2), n-1) Println(mint.Wrap(ans)) } /* 考察 |Qi-Qj|の値Dごとに和sum[D]を求めると D=1 sum[1] = |2-1|+|3-2|+|4-3|+ ... + |(N-1)-(N-2)|+|N-(N-1)| = 1 * (N-1) D=2 sum[2] = |3-1|+|4-2|+|5-3|+ ... + |(N-1)-(N-3)|+|N-(N-2)| = 2 * (N-2) D=3 sum[3] = |4-1|+|5-2|+|6-3|+ ... + |(N-1)-(N-4)|+|N-(N-3)| = 3 * (N-3) ... D=N-3 sum[N-3] = |(N-2)-1|+|(N-1)-2|+|N-3| = (N-3) * 3 = (N-3) * (N - (N-3)) D=N-2 sum[N-2] = |(N-1)-1|+|N-2| = (N-2) * 2 = (N-2) * (N - (N-2)) D=N-1 sum[N-1] = |N-1| = (N-1) * 1 = (N-1) * (N - (N-1)) 規則性があるぽく見えるので D=1..(N-1) sum[1..(N-1)] = 1*(N-1) + 2*(N-2) + ... + (N-1)*(N-(N-1)) = (1 + 2 + ... + (N-1))*N - (1*1 + 2*2 + ... + (N-1)*(N-1)) = Nsum(N-1)*N - N2sum(N-1) (※ Nsum(N) ... 1~Nまでの総和) (※ N2sum(N) ... 1~Nまでの二乗和) 例えば周遊コストの計算式に (8,3) の組み(|8-3|または|3-8|)が発生するのは 2*N*(N-2)! 通り なので答えは ANSWER = sum[1..(N-1)] * 2*N*(N-2)! / N! = sum[1..(N-1)] * 2 / (N-1) = (Nsum(N-1)*N - N2sum(N-1)) * 2 / (N-1) */ type Mint struct { Mod int ModInt *Int invCache map[int]int } func newMint(mod int) *Mint { return &Mint{ Mod: mod, ModInt: NewInt(int64(mod)), invCache: make(map[int]int), } } func (mint *Mint)wrap(a int) int { return a%mint.Mod } func (mint *Mint)Wrap(a int) int { return mint.add(mint.wrap(a),mint.Mod) } func (mint *Mint)add(a, b int) int { return mint.wrap(a+b) } func (mint *Mint)Add(a int, bs ...int) int { a = mint.wrap(a) for _, b := range bs { a = mint.add(a, mint.wrap(b)) } return a } func (mint *Mint)sub(a, b int) int { return mint.wrap(a-b) } func (mint *Mint)Sub(a int, bs ...int) int { a = mint.wrap(a) for _, b := range bs { a = mint.sub(a, mint.wrap(b)) } return a } func (mint *Mint)mul(a, b int) int { return mint.wrap(a*b) } func (mint *Mint)Mul(a int, bs ...int) int { a = mint.wrap(a) for _, b := range bs { a = mint.mul(a, mint.wrap(b)) } return a } func (mint *Mint)inv(a int) int { if v, ok := mint.invCache[a]; ok { return v } x := int(new(Int).ModInverse(NewInt(int64(a)), mint.ModInt).Int64()) mint.invCache[a] = x return x } func (mint *Mint)Inv(a int) int { return mint.inv(mint.wrap(a)) } func (mint *Mint)div(a, b int) int { return mint.wrap(a*mint.inv(b)) } func (mint *Mint)Div(a int, bs ...int) int { a = mint.wrap(a) for _, b := range bs { a = mint.div(a, mint.wrap(b)) } return a } func (mint *Mint)Nsum(n int) int { return mint.Div(mint.Mul(n, n+1), 2) } func (mint *Mint)N2sum(n int) int { return mint.Div(mint.Mul(n, n+1, 2*n+1), 6) }