Eli最近迷上了汉诺塔。她玩了传统汉诺塔后突发奇想,发明了一种新的汉诺塔玩法。 有A、B、C三个柱子顺时针放置,移动的次序为A仅可以到B,B仅可以到C、C仅可以到A。即只可顺时针移动,不可逆时针移动。当然,汉诺塔的普适规则是适用的:每次移动后,大金片必须在小金片的下面。 现在A柱子上有个金片。Eli想知道,她把这些全部移动到B或C,分别要多少次操作?
输入描述:
一个正整数。


输出描述:
两个整数,分别代表A移到B和A移到C的最少操作数。由于该数可能过大,你需要对1000000007取模。
示例1

输入

2

输出

5 7

说明

A移到B的5步:A->B  B->C  A->B  C->A  A->B
A移到C的7步:A->B  B->C  A->B  C->A  B->C  A->B  B->C

加载中...