题目描述

现在要求你使用 n 个点去构造一张无向连通图。其中，定义每条连边的长度为 1 。

显然此时每个点到 1 号点会有最短的路径距离。我们记点 1 到点 i 的最短路径距离为 $d_i$ 。

你构造的图要满足：对于点 1∼ 点 n−1 的最短路径，要比点 到点 n 的最短路径短。

或者用数学语言描述：对于任意 $1≤i≤n−1,i∈N_+$ ，要求 $d_i<d_n$你的任务是计算可以构造出多少满足上述要求的图。

两个图被视为不同的，当且仅当至少有一条连边在一个图中出现，而另一个图中没有。

例如当 n=3 时，只有 1 个满足条件的方案. 该方案中,$d_1=0,d_2=1,d_3=2$，满足要求。

由于本题的答案可能很大，仅要求输出方案数对 $10^9+7$ 取模后的结果。

输入格式

一行一个正整数，表示点数 n。

输出格式

一行一个整数表示答案对 $10^9+7$ 取模后的结果。

输入输出样例 #1

输入 #1

3

输出 #1

1

输入输出样例 #2

输入 #2

4

输出 #2

8

说明/提示

对于前10%的数据，保证$n=5$

对于另外10%的数据，保证$n=6$

对于另外30%的数据，保证$10≤n≤20$

对于剩下的50%的数据，保证$100≤n≤500$