Problem4661--体育课

4661: 体育课

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

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

Input

一行一个正整数 nnn

Output


Sample 1 Input

3

Sample 1 Output

166374063

HINT

【数据规模】
对于 30%30\%30% 的数据,n≤10n \leq 10n10
对于 50%50\%50% 的数据,n≤15n \leq 15n15
对于 70%70\%70% 的数据,n≤2000n \leq 2000n2000
对于 90%90\%90% 的数据,n≤105n \leq 10^5n105
对于 100%100\%100% 的数据,n≤107n \leq 10^7n107
【样例解释】

其中 xxx 代表号码为 xxx 的卡牌,若 xxx 出现了两次,则第一次表示翻开又合上了 xxx,第二次表示永久翻开了xxx

Source/Category