SPOJ - LOCKER
https://vjudge.net/problem/45908/origin
暴力枚举2～10
2 2
3 3
4 2 2
5 2 3
6 3 3
7 2 2 3
8 2 3 3
9 3 3 3
发现是在没有1的情况下，3尽可能的多，其他用2补。
大于等于10的，可以由10以内的凑出来，就可以递推出去了

#include <iostream>
#include <cstdio>
#define p(a) putchar(a)
#define mod 1000000007
#define For(i,a,b) for(long long i=a;i<=b;++i)

using namespace std;
long long T,n,x,y;

long long ksm(long long a,long long b){
    long long r=1;
    while(b>0){
        if(b&1)
            r=r*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return r;
}

int main(){
    cin>>T;
    while(T--){
        cin>>n;
        if(n<=4)
            cout<<n;
        else
            if(n%3==0)
                cout<<ksm(3,n/3);
            else
                if((n-2)%3==0)
                    cout<<2*ksm(3,(n-2)/3)%mod;
                        else
                            if((n-4)%3==0)
                                cout<<4*ksm(3,(n-4)/3)%mod;
        p('\n');
    }
    return 0;
}