懒得写矩阵快速幂了

n = int(input())
a,b,c = 1,1,0
for _ in range(n-3):
    a,b,c = a+2*b+c,a,b
print(a)