徐老师的最短路问题
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
说明
徐老师最近在给同学们上《最短路》这节课，上完课自然就要做题，而做题自然就需要老师出数据所以现在徐老师需要构造一张有 $n$ 个点的无向连通图，为了简单一些，这张图的边权都为 $1$，只需要连边就可以了
当构造完这张图以后，徐老师会以 $1$ 为起点跑一遍 $dijkstra$ 算法，计算出 $dis_i$ 表示 $1$ 出发到达 $i$ 的最短路径长度
为了方便，徐老师希望构造出来的图使得 $n$ 的最短路是最大且唯一的，即 $dis_n > dis_i(1 \leq i < n)$
现在徐老师想知道，他一共有多少种不同的构图方案？
输入格式
输入一个整数 $n$ 表示徐老师需要构造一张大小为 $n$ 的图
| 测试点编号 | $n$ |
| :---: | :---: |
| $1$ | $n=5$ |
| $2$ | $n=6$|
| $3 \sim 5$ | $10 \leq n \leq 20$|
| $6 \sim 10$ | $100 \leq n \leq 500$|
| :---: | :---: |
| $1$ | $n=5$ |
| $2$ | $n=6$|
| $3 \sim 5$ | $10 \leq n \leq 20$|
| $6 \sim 10$ | $100 \leq n \leq 500$|
输出格式
输出一个整数表示答案，由于答案可能很大，请将答案对 $1e9+7$ 取模样例
48提示
对于样例 $1$，只能是 $1 \leftrightarrow 2 \leftrightarrow 3$23CSP-S秋季提高组模拟赛(8)
- 状态
- 已结束
- 规则
- ACM/ICPC
- 题目
- 3
- 开始于
- 2023-10-4 17:30
- 结束于
- 2023-10-14 17:30
- 持续时间
- 240 小时
- 主持人
-
huangzhe
- 参赛人数
- 21
