解题思路

根据题意，金片只能从一根柱子上顺时针移动到下一个柱子上，而不能反过来移动，因此我们只需要考虑两种情况。

1、将n个金片移动到顺时针的下一个柱子上。所需的次数记为 move1[n]

2、将n个金牌移动到逆时针的上一个柱子上，相当于是顺时针移动两次。所需的次数记为 move2[n]

现在要做的是，推导 move1[n + 1] 和 move2[n + 1] 。

我们先看 move1[n + 1] 。不妨假设现在要将n + 1个金片从A柱子移动到B柱子，那么可以把过程拆分为几个步骤：

1、把n个金片从A移动到C，所需次数为 move2[n]。

2、将最下面的一个金片从A移动到B，记移动1次。

3、最后将C上的n个金片移动到B，所需次数为 move2[n]。

整理成式子就是 move1[n + 1] = move2[n] * 2 + 1

再看 move2[n + 1]。同样不妨假设现在要将n + 1个金片从A柱子移动到C柱子，那么可以把过程拆分为几个步骤：

1、把n个金片从A移动到C，所需次数为 move2[n]。

2、将最下面的一个金片从A移动到B，记移动1次。

3、将C上的n个金片移动到A，所需次数为 move1[n]。

4、步骤2中移动到B上的金片移动到C，记移动1次。

5、将A上的n个金片移动到C，所需次数为 move2[n]。

整理成式子就是 move2[n + 1] = move2[n] * 2 move1[n] + 2

推导出这两个公式后，写代码就很简单了。

注意初始状态：move1[1] = 1 ， move2[1] = 2

以上的推导过程也可以看成是动态规划，两个式子就是动态转移方程。

#include <iostream>
#include <vector>
using namespace std;

const int mod = 1000000007;

int main() {
    int n;
    cin >> n;
    vector<long long> move1(n + 1);
    vector<long long> move2(n + 1);
    move1[1] = 1;
    move2[1] = 2;
    for(int i = 1; i < n; ++i) {
        move1[i + 1] = (move2[i] * 2 + 1) % mod;
        move2[i + 1] = (move2[i] * 2 + move1[i] + 2) % mod;
    }
    cout << move1[n] << " " << move2[n];
}