4661: 体育课
[Creator : ]
Description
你在上体育课。
课上,同学们在玩游戏。游戏内容为:每队同学站在 505050 米起点,505050 米终点有 101010 张卡片,上面写着号码 111 至 101010,卡片打乱且数字面朝跑道放着。也就是说你不可以看见每张卡片的数字。
每队的目标都是将卡片从 111 到 101010 按顺序翻开。
每一回合,每队将有一名同学从起点跑到终点,翻开一张卡片。如果该卡片的号码是当前需要翻开的,则将其翻开,否则继续将卡片倒放在跑道上。也就是说,如果你翻错了,你的操作即视为无效,但你可以记住该卡片的号码及位置,因为每回合卡片是不会重新打乱的。
当你把卡片从 111 到 101010 翻开后,你的小队获得胜利。
你想知道,你的期望花费回合数为多少。
因为只有 101010 张卡片,所以聪明的你马上想出答案。但是如果是 nnn 张卡片呢?
课上,同学们在玩游戏。游戏内容为:每队同学站在 505050 米起点,505050 米终点有 101010 张卡片,上面写着号码 111 至 101010,卡片打乱且数字面朝跑道放着。也就是说你不可以看见每张卡片的数字。
每队的目标都是将卡片从 111 到 101010 按顺序翻开。
每一回合,每队将有一名同学从起点跑到终点,翻开一张卡片。如果该卡片的号码是当前需要翻开的,则将其翻开,否则继续将卡片倒放在跑道上。也就是说,如果你翻错了,你的操作即视为无效,但你可以记住该卡片的号码及位置,因为每回合卡片是不会重新打乱的。
当你把卡片从 111 到 101010 翻开后,你的小队获得胜利。
你想知道,你的期望花费回合数为多少。
因为只有 101010 张卡片,所以聪明的你马上想出答案。但是如果是 nnn 张卡片呢?
Input
一行一个正整数 nnn。
Output
Sample 1 Input
3
Sample 1 Output
166374063