233的树

题号：NC247066
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

读入一个数 $n$ ，代表树的点数为 $n$

记 $f(d_1,d_2,...,d_n)$ 代表 $n$ 个点的度数分别为 $d_i$ 的情况下，树的直径的最大值（若不能构成树, $f(d_1,d_2,...,d_n)=0$ )

树的直径: 树上距离最远的两点间的距离

树上两点间距离:两点之间路径上的点数(包括自己)

求满足 $d_i$ 是正整数的情况下， $\sum f(d_1,d_2,...,d_n)$ 的值,答案对 $10^9+7$ 取模

输入描述:

第一行一个正整数 ${n}$

${2\le n \le 10^6}$

输出描述:

输出一行一个数代表答案

示例1

输入

复制

输出

复制