思路

dp

过程

代码

#include <iostream>

using namespace std;

const int MOD = 1000000007;

int n;

int main()
{
    cin >> n;
    long long x = 1, y = 2;
    for(int i = 2;i <= n;i ++)
    {
        long long tmp1 = x, tmp2 = y;
        x = (2 * tmp2 + 1) % MOD;
        y = (2 * tmp2 + tmp1 + 2) % MOD;
    }
    cout << x << " " << y << endl;
    return 0;
}