Torni

#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
#define F first
#define S second

using namespace std;

ll dp[1010101][2];
const ll M=1e9+7;

void dfs() {
	dp[1][0]=1;
	dp[1][1]=1;
	for (int j=2;j<1010101;j++) {
		dp[j][0]=(4*dp[j-1][0]+dp[j-1][1])%M;
		dp[j][1]=(dp[j-1][0]+2*dp[j-1][1])%M;
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	dfs();
	int tst;
	cin>>tst;
	for (int t=0;t<tst;t++) {
		int n;
		cin>>n;
		cout<<(dp[n][0]+dp[n][1])%M<<"\n";
	}
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: ACCEPTED