TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P5908
  • 問題
  • P5908【宽容的欢乐赛】都不容易
    制限 : 時間制限 : - MS   メモリ制限 : 262144 KB
    問題説明

    nodgd现在是南开的信息学竞赛教练,虽然工资很低,但在昔日的小伙伴眼中nodgd就是个土豪。每当昔日的小伙伴缺钱来找nodgd借钱时,nodgd就会以“钱也不是天上掉下来的,赚钱养家也都不容易”这样的借口推辞。每当nodgd缺钱去找昔日的小伙伴借钱,nodgd会说“这么多年的友情也都不容易,不要因为借钱这么点小事情破坏了感情”。久而久之,nodgd就没有小伙伴了。

    nodgd上次借小伙伴的钱买了一套积木。积木共有$n$块,每块形状相同但颜色不同。每块积木都有大小两端,一块积木的大端可以和另一块积木的小端连接起来,特别的,同一块积木的大小两端也可以连接起来。如果将若干块积木的大小端首尾连接起来,就形成了一个积木圈。为了方便携带,nodgd将$n$块积木连接成若干个积木圈后,用一个绳圈将它们串起来。虽然积木圈有大有小,但串在绳圈上后它们的相对位置就不会发生变化。

    一天,nodgd突发奇想,打算枚举所有将$n$个积木都挂到绳圈上的方案。聪明的nodgd掐指一算,发现方案非常多,但具体是多少nodgd才懒得算——他让你帮他算!你只要告诉nodgd方案数$\mod{1,000,000,007}$ 后的结果即可。

    入力形式

    输入共$1$行,有一个整数$n$,表示积木的总数。

    出力形式

    输出一行,一个整数,表示方案数$\mod{1,000,000,007}$ 的结果。

    サンプル入力 1

    3

    サンプル出力 1

    6

    サンプル入力 2

    4

    サンプル出力 2

    26

    ヒント

    样例说明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$。


    ソース  感谢nodgd命题