题解 | #愉快的递推式#

令 ，

则有 ，

由于答案对 取模，取分数 对 的逆元即可。

现在问题转化为了已知问题，即得。

if 1:
    inf = float('inf')
    import sys
    input = lambda: sys.stdin.readline().strip()
    I = lambda: input()
    II = lambda: int(input())
    IS = lambda: input().split()
    MII = lambda: map(int, input().split())
    LMII = lambda: list(map(int, input().split()))
    L01 = lambda: list(int(x) for x in input())
    LMZ = lambda A: list(map(list, zip(*A)))
    from collections import deque,defaultdict,Counter

MOD = 10 ** 9 + 7

class Mat:
    __slots__ = ('a',)

    def __init__(self, n, ident = False):
        self.a = [[0]*n for _ in range(n)]
        if ident:
            for i in range(n):
                self.a[i][i] = 1

    def __mul__(self, other):
        n = len(self.a)
        res = Mat(n)
        A, B, C = self.a, other.a, res.a
        for i in range(n):
            for k in range(n):
                if A[i][k] == 0: continue
                for j in range(n):
                    C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD
        
        return res

    def mat_pow(base, k):
        n = len(base.a)
        res = Mat(n, ident=True)
        while k:
            if k & 1: res = res * base
            base = base * base
            k >>= 1
        return res

def qpow(x, k, MOD):
    if x == 0: return 0
    res = 1
    while k:
        if k & 1: res = res * x % MOD
        x = x * x % MOD
        k >>= 1
    return res


def Solve():
    x = II()
    if x == 1 or x == 2:
        print(1)
        return

    base = Mat(2)
    base.a = [[3, 2],
              [1, 0]]

    R = base.mat_pow(x - 2)

    inv2 = pow(2, MOD - 2, MOD)
    a1 = a2 = 3 * inv2

    an = (R.a[0][0] * a1 + R.a[0][1] * a2) % MOD
    print(f"{(an - inv2) % MOD:.0f}")

    
if __name__ == '__main__':
    T = 1
    # T = int(input())
    for i in range(T):
        Solve()