生成树计数

发布时间: 2018年1月29日 10:26   最后更新: 2018年2月11日 23:54   时间限制: 1000ms   内存限制: 128M

OneDay最近对生成树(包含所有顶点的联通无环子图。)非常的感兴趣,他想知道对于特定的简单平面无向图是不是存在求生成树个数的简单方法。

OneDay定义了这样的图:一个以$\lbrace 0,1,2,…,n \rbrace$为顶点的图,顶点$0$与其它$n$个顶点直接相连,对于顶点$i(1≤i<n)$,顶点$i$与顶点$i+1$连有一条边。下面是$n=4$的图:

 

image.png

请问对于任意$n$,这样的图的生成树个数。

有多组测试数据(数据组数$≤50$)。对于每组数据,有一个整数$n$。
$1≤n≤10^9$

对于每组测试数据,输出所求得的答案(对$10^9+7$取模)。

复制
1
2
1
3

math dp

Weekly Training 2018.1.28