Shared code

#include <bits/stdc++.h>

using namespace std;

bool equals(int x, vector<int> y){
	for(int i=0;i<y.size();i++)
		if(x==y[i])
			return true;
	return false;
}

int main(){
	long long int m = 1000000007;
	long long int dp[21] = {0};
	long long int solution[1000000];
	solution[0] = 2;
	
	dp[1] = 1;
	dp[2] = 1;
	dp[7] = 1;
	dp[8] = 1;
	dp[11] = 1;
	dp[12] = 1;

	vector<int> two = {1,3,6,8,10,13};

	for(int i=1;i<1000000;i++){
		long long int total=0;
		for(int j=1;j<21;j++){
			if(equals(j,two)){
				total += 2*dp[j];
				total %= m;
			}
			else{
				total += dp[j];
				total %= m;
			}
		}
		solution[i] = total;
		long long int tmp[21] = {0};
		tmp[1] = dp[1] + dp[3] + dp[6] + dp[8] + dp[10] + dp[13];
		tmp[2] = tmp[1];
		tmp[3] = dp[2] + dp[9];
		tmp[4] = dp[5] + dp[7] + dp[16] + dp[19];
		tmp[5] = dp[4] + dp[11] + dp[18] + dp[20];
		tmp[6] = tmp[4];
		tmp[7] = tmp[1];
		tmp[8] = tmp[1];
		tmp[9] = tmp[3];
		tmp[10]= tmp[5];
		tmp[11]= tmp[1];
		tmp[12]= tmp[1];
		tmp[13]= dp[12] + dp[14] + dp[15] + dp[17];
		tmp[14]= tmp[13];
		tmp[15]= tmp[4];
		tmp[16]= tmp[13];
		tmp[17]= tmp[5];
		tmp[18]= tmp[13];
		tmp[19]= tmp[4];
		tmp[20]= tmp[5];
		
		for(int j=1;j<21;j++)
			dp[j] = tmp[j] % m;
	}
	int t; cin >> t;
	while(t--){
		int n; cin >> n;
		cout << solution[n-1] << endl;
	}
	return 0;
}