UOJ Logo LFYZ Online Judge

LFYZOJ

#341. 【杭电 4624】无穷动(Endless Spin)

统计

题目描述

n 个白球,每次随机选择一段区间染黑,求使所有球都为黑色的次数期望。

注意,此处要求结果对 20,180,801(为质数)取模,而非原题的保留 15 位小数。

输入输出格式

输入一整数 n,输出一整数代表答案。

样例

Input

3

Output

2018083

Explanation

样例结果为 2.9。

数据范围

$n\in [1..50]$。

时限 2s,空限 32M

原题链接,作者 WJMZBMR,来源 2013 多校 3。侵删。