Torni

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
typedef long long ll;
 
const int M = 1e9 + 7;
const int N = 1e6 + 5;
 
ll ans[N];
ll s[N];
ll po[N];
ll s2[N];
 
int main() {
	po[0] = 1;
	po[1] = 1;
	for(int i = 2; i < N; ++i) {
		po[i] = 4*po[i-1];
		po[i] %= M;
	}
 
	ans[0] = 1;
	s[0] = 1;
 
	for(int i = 1; i < N; ++i) {
		if(i <= 3) {
			for(int j = 1; j < i; ++j) {
				s2[i] += po[j]*s[i-j-1];
				s2[i] %= M;
			}
		} else {
			s2[i] = s2[i-1]*4;
			s2[i] %= M;
			s2[i] += s[i-2];
			s2[i] %= M;
		}
		ans[i] = s[i-1] + s2[i] + po[i];
		ans[i] %= M;
		s[i] = s[i-1] + ans[i];
		s[i] %= M;
	}
 
 
	int t;
	cin >> t;
	for(int i = 1; i <= t; ++i) {
		int n;
		cin >> n;
		cout << ans[n] << "\n";
	}
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: ACCEPTED