题解 | 循环汉诺塔

import sys

# 14:44

# 1. 分解子问题，还是分为挪底部（最后一块）和顶部（前n-1)块
# 2. A-->B的时候，先把前n-1块从A挪到B，再从B挪到C，再把底部挪到B，再把顶部从C挪到A再挪到B
# 注意，顶部A-->C, 和最后C-->A的步数一样，都是把n-1挪两个盘
# 因此 AB(N) = 2 AC(N-1) + 1
# 3. A-->C的时候，先把顶部挪到B在挪到C,即AC(N-1), 底部A挪到B，一步，再把顶部从C挪到A，即挪一个盘=AB(N-1)，再把底部从B挪到C，一个步骤， 再把顶部从A挪到C，即AC(N-1)
# AC(N) = 2AC(N-1) + AB(N-1) + 2
# 尴尬，pythonO(N)最后一个也过不了， 估计只能用数学归纳做
# 动态规划

n = int(input())

last_ab = 1 # 也可以理解为挪一个盘的步骤
last_ac = 2 # 也可以理解为挪两个盘的步骤
p=1000000007

for i in range(2,n+1):
    now_ab = 2 * last_ac + 1
    now_ac = 2 * last_ac + last_ab + 2
    last_ab, last_ac = now_ab%p, now_ac%p # (a+b)%p = (a%p+b%p)%p


print(last_ab, last_ac)