code：

    if n==0:
        return 1
    ans = pow_mod(a,n//2,mod)**2%mod
    if n%2==1:
        ans = ans*a%mod
    return ans

n = -1
mod = 1000000000
while n:
    n = int(input())
    if n==0:
        break
    elif n<4:
        print('0')
        continue
    else:
        x = n-4
    print((pow_mod(-4,x,mod)+6*pow_mod(4,x,mod)-64*pow_mod(8,x,mod)+81*pow_mod(12,x,mod))%mod)

（疑似常数过大）