for(int i=3;i<=1000;i++){
			ai[i]=ai[i-1]+ai[i-2]*4;int t=2;
			for(int j=i-3;j>=1;j--){
				ai[i]=ai[i]+ai[j]*t;
				if(t==2){
					t=3;
				}else{
					t=2;
				}
			}
			ai[i]=ai[i]+t;
		
		}