60分代码：

#include<bits/stdc++.h>
#define mod 1000000000
#define phi 400000000
#define B 500000
using namespace std;
long long n,Mul1[B][10],Mul2[B][10];
long long query1(long long x){
    long long sum,res=0;
    sum=1;
    for(int i=1;i<=n;i++)sum*=12;
    res+=sum;
    sum=1;
    for(int i=1;i<=n;i++)sum*=8;
    res-=4*sum;
    sum=1;
    for(int i=1;i<=n;i++)sum*=4;
    res+=4*sum;
    sum=1;
    for(int i=1;i<=n;i++)sum*=-4;
    res+=sum;
    return res/256;
}
long long fpow(int p,long long y){
    return (Mul1[y/B][p]*Mul2[y%B][p])%mod;
}
long long query2(long long x){
    int res=0;
    res+=(81*fpow(1,x-4))%mod;
    res=(res-fpow(2,x-2)+mod)%mod;
    res=(res+6*fpow(3,x-4))%mod;
    res=(res+fpow(4,x-4))%mod;
    return res;
}
int main(){
    Mul1[0][1]=Mul2[0][1]=1;
    for(int i=1;i<=B;i++)Mul2[i][1]=(Mul2[i-1][1]*12)%mod;
    for(int i=1;i<=B;i++)Mul1[i][1]=(Mul1[i-1][1]*Mul2[B][1])%mod;
    Mul1[0][2]=Mul2[0][2]=1;
    for(int i=1;i<=B;i++)Mul2[i][2]=(Mul2[i-1][2]*8)%mod;
    for(int i=1;i<=B;i++)Mul1[i][2]=(Mul1[i-1][2]*Mul2[B][2])%mod;
    Mul1[0][3]=Mul2[0][3]=1;
    for(int i=1;i<=B;i++)Mul2[i][3]=(Mul2[i-1][3]*4)%mod;
    for(int i=1;i<=B;i++)Mul1[i][3]=(Mul1[i-1][3]*Mul2[B][3])%mod;
    Mul1[0][4]=Mul2[0][4]=1;
    for(int i=1;i<=B;i++)Mul2[i][4]=(Mul2[i-1][4]*(mod-4))%mod;
    for(int i=1;i<=B;i++)Mul1[i][4]=(Mul1[i-1][4]*Mul2[B][4])%mod;
    while(1){
        cin>>n;
        if(!n)return 0;
        if(n<=4)cout<<query1(n)%mod<<endl;
        else cout<<query2(n)<<endl;
    }
}

几乎全WA的代码：

#include<bits/stdc++.h>
#define mod 1000000000
#define phi 400000000
#define B 500000
using namespace std;
long long n,Mul1[B][10],Mul2[B][10];
long long query1(long long x){
    long long sum,res=0;
    sum=1;
    for(int i=1;i<=n;i++)sum*=12;
    res+=sum;
    sum=1;
    for(int i=1;i<=n;i++)sum*=8;
    res-=4*sum;
    sum=1;
    for(int i=1;i<=n;i++)sum*=4;
    res+=4*sum;
    sum=1;
    for(int i=1;i<=n;i++)sum*=-4;
    res+=sum;
    return res/256;
}
long long fpow(int p,long long y){
   // if(y>(long long)B*B)exit(0);
    return (Mul1[y/B][p]*Mul2[y%B][p])%mod;
}
long long query2(long long x){
    int res=0;
    res+=(81*fpow(1,x-4))%mod;
    res=(res-fpow(2,x-2)+mod)%mod;
    res=(res+6*fpow(3,x-4))%mod;
    res=(res+fpow(4,x-4))%mod;
    return res;
}
int main(){
    Mul1[0][1]=Mul2[0][1]=1;
    for(int i=1;i<=B;i++)Mul2[i][1]=(Mul2[i-1][1]*12)%mod;
    for(int i=1;i<=B;i++)Mul1[i][1]=(Mul1[i-1][1]*Mul2[B][1])%mod;
    Mul1[0][2]=Mul2[0][2]=1;
    for(int i=1;i<=B;i++)Mul2[i][2]=(Mul2[i-1][2]*8)%mod;
    for(int i=1;i<=B;i++)Mul1[i][2]=(Mul1[i-1][2]*Mul2[B][2])%mod;
    Mul1[0][3]=Mul2[0][3]=1;
    for(int i=1;i<=B;i++)Mul2[i][3]=(Mul2[i-1][3]*4)%mod;
    for(int i=1;i<=B;i++)Mul1[i][3]=(Mul1[i-1][3]*Mul2[B][3])%mod;
    Mul1[0][4]=Mul2[0][4]=1;
    for(int i=1;i<=B;i++)Mul2[i][4]=(Mul2[i-1][4]*(mod-4))%mod;
    for(int i=1;i<=B;i++)Mul1[i][4]=(Mul1[i-1][4]*Mul2[B][4])%mod;
    while(1){
        cin>>n;
        if(!n)return 0;
        if(n<=4)cout<<query1(n)%mod<<endl;
        else cout<<query2(n)<<endl;
    }
}