P5908【宽容的欢乐赛】都不容易 | |
|
Description
nodgd现在是南开的信息学竞赛教练,虽然工资很低,但在昔日的小伙伴眼中nodgd就是个土豪。每当昔日的小伙伴缺钱来找nodgd借钱时,nodgd就会以“钱也不是天上掉下来的,赚钱养家也都不容易”这样的借口推辞。每当nodgd缺钱去找昔日的小伙伴借钱,nodgd会说“这么多年的友情也都不容易,不要因为借钱这么点小事情破坏了感情”。久而久之,nodgd就没有小伙伴了。
nodgd上次借小伙伴的钱买了一套积木。积木共有$n$块,每块形状相同但颜色不同。每块积木都有大小两端,一块积木的大端可以和另一块积木的小端连接起来,特别的,同一块积木的大小两端也可以连接起来。如果将若干块积木的大小端首尾连接起来,就形成了一个积木圈。为了方便携带,nodgd将$n$块积木连接成若干个积木圈后,用一个绳圈将它们串起来。虽然积木圈有大有小,但串在绳圈上后它们的相对位置就不会发生变化。
一天,nodgd突发奇想,打算枚举所有将$n$个积木都挂到绳圈上的方案。聪明的nodgd掐指一算,发现方案非常多,但具体是多少nodgd才懒得算——他让你帮他算!你只要告诉nodgd方案数$\mod{1,000,000,007}$ 后的结果即可。
Input Format
输入共$1$行,有一个整数$n$,表示积木的总数。
Output Format
输出一行,一个整数,表示方案数$\mod{1,000,000,007}$ 的结果。
Sample Input 1
3
Sample Output 1
6
Sample Input 2
4
Sample Output 2
26
Hint
样例说明1
共有$3$个积木,不妨编号为$1,2,3$。
将积木$1$、积木$2$、积木$3$连接在一起形成一个积木圈,有$2$种情况,分别是$(1\to2\to3\to1)$和$(1\to3\to2\to1)$;每种情况都有$1$种串在绳圈上的方案,共$2$种方案。
将积木$1$单独连接成积木圈,积木$2$和积木$3$连接在一起形成一个积木圈,有$1$种情况,即$(1\to1)(2\to3\to2)$;这$1$种情况有$1$种串在绳圈上的方案,共$1$种方案,即$(1\to1)-(2\to3\to2)-(1\to1)$。
将积木$2$单独连接成积木圈,积木$1$和积木$3$连接在一起形成一个积木圈,同上,共$1$种方案。
将积木$3$单独连接成积木圈,积木$1$和积木$2$连接在一起形成一个积木圈,同上,共$1$种方案。
将三个积木都单独连接成积木圈,有$1$种情况;将三个积木圈串在绳圈上,共有$1$种方案,即$(1\to1)-(2\to2)-(3\to3)-(1\to1)$。绳圈可以翻转,将$(1\to1)-(2\to2)-(3\to3)-(1\to1)$翻转后得到$(1\to1)-(3\to3)-(2\to2)-(1\to1)$,这两个方案视为相同的方案。
综上,$n=3$时共有$2+1+1+1+1=6$种方案。
样例说明2
我有一个绝妙的样例说明,可惜这里太小,我写不下。
数据规模与约定
对于30%的数据,\(n\le10\);
对于70%的数据,\(n\le200\);
对于100%的数据,$1\le n\le5000$。