Torni

#include <iostream>
#include <algorithm>
#include <vector>

const int MOD = 1000000007;
const int MAX = 1000009;

long tapoja2[MAX], tapoja12[MAX];

int main() {
	long tapoja1 = 1, tapoja2_sum = 0, tapoja12_sum = 0, haxum = 0;
	for (long n = 1; n < MAX; ++n) {
		tapoja2[n] = 1 + tapoja2_sum + tapoja12_sum;
		tapoja2[n] %= MOD;

		tapoja2_sum += tapoja2[n];
		tapoja2_sum %= MOD;

		haxum *= 4;
		haxum += tapoja2[n - 1];
		haxum %= MOD;

		tapoja12[n] = haxum + tapoja1;
		tapoja1 = (tapoja1 * 4) % MOD;
		tapoja12[n] %= MOD;
		tapoja12_sum += tapoja12[n];
		tapoja12_sum %= MOD;
	}

	int t;
	std::cin >> t;
	for (int i = 0; i < t; ++i) {
		int n;
		std::cin >> n;
		std::cout << ((tapoja2[n] + tapoja12[n]) % MOD) << std::endl;
	}
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: ACCEPTED