圣庙里的汉诺塔[HA-SY,COGS]

成绩 开启时间 2014年09月19日 星期五 10:07
折扣 0.8 折扣时间 2014年09月26日 星期五 10:07
允许迟交 是 关闭时间 2014年09月26日 星期五 10:07
输入文件 Hanoia.in 输出文件 Hanoia.out

【题目描述】

法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的N片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。


有预言说，这件事完成时宇宙会在一瞬间闪电式毁灭。也有人相信婆罗门至今还在一刻不停地搬动着圆盘。

若挪动一次耗时1秒，请计算这个世界存在的时间。

【输入格式】

输入N(1≤N≤2^64-1)

【输出格式】

输出时间 mod 999,999,997(一个整数)。

【样例输入】 

3

【样例输出】 

7

【来源】

Henan Expermental High School[HA-SY] ,www.cojs.tk[COGS],CH.