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

Grade Open Time Friday, 19 September 2014, 10:07 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:07 am
Allow late Yes Close Time Friday, 26 September 2014, 10:07 am
Input file Hanoia.in Output file 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.