#P6836. 树

    ID: 6668 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2400提高+/省选-期望线性性几何分布独立集插板法重复元素除重阶乘逆元预处理快速幂

树

题目描述

有 nn 个位置排成一个圆环,起初都没有树。每次等概率独立地选一个位置并种树。选到已有树的位置也照常计一次。若某个还没有树的位置的两个相邻位置都有树,它会自动长出一棵树。自动长树不占用选择次数。

当每个位置都有树时,游戏结束。求选择次数的期望。n=1n=1 时一次选择即可结束。n=2n=2 时,一个位置的两个相邻位置均指另一个位置。

输入格式

一行一个整数 nn。

输出格式

一行一个整数,表示期望对 109+710^9+7 取模的结果。分数 a/ba/b 按 a⋅b−1a\cdot b^{-1} 计算。

样例

2
1
5
166666673
10
698412717

数据范围

1≤n≤1071\le n\le10^7。对于 20%、40%、50%、70% 的数据,依次有 n≤20,40,500,5000n\le20,40,500,5000。

YOIP Practice #7。原题面 PDF