Untitled

#define MOD 1000000007

vector< int > ways(vector< int > nvalues) {
    vector< long long int > dp;
    dp.resize(1100000);

    dp[2] = 9;
    dp[1] = 2;
    dp[0] = 1;

    for (int i = 3; i <= 1000000; i++) {
        dp[i] = (dp[i-1] * 3) % MOD;
        dp[i] += (dp[i-2] * 3) % MOD;
        dp[i] = (dp[i] + MOD) - (dp[i-3] * 1) % MOD;
        dp[i] %= MOD;
    }

    vector< int > ans;

    for (int i = 0; i < nvalues.size(); i++) {
        ans.push_back((int) dp[nvalues[i]]);
    }

    return ans;
}