题目链接

小dp：f_i 表示走了i步，位置在原点的方案数，g_i 表示走了i步，位置不在原点的方案数。所以f_i = 3 * g_i-1，g_i = f_i-1 + 2 * g_i-1。

code：

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
#define int long long 
const int N = 1e5 + 100;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;

signed main(int argc, char const *argv[]) {
    int n, f = 0, g = 1;
    cin >> n;
    for (int i = 2; i <= n; i++) {
        int t = f;
        f = 3 * g % mod;
        g = (t + 2 * g) % mod;
    }
    cout << f << endl;
    return 0;
}