#include <bits/stdc++.h>

using namespace std;

//*************************************************************************
// HackerRank Prepare > Mathematics > Fundamentals: Summing the N series
//*************************************************************************

string ltrim(const string &);
string rtrim(const string &);

std::mutex result_mutex;
std::mutex cvwait_mutex;

std::condition_variable cv;

static constexpr long MOD = (long) pow(10, 9) + 7;
static constexpr int maxTestCases = 10;

int results[maxTestCases];
int maxConcurrentThreads = 4;
int numTestCases;

std::atomic<int> numRunningThreads(0);

enum struct OutputMode { HackerRank, Linux };

OutputMode outputMode = OutputMode::Linux;

void summingSeries(long n, size_t index, bool should_wait)
{
    cerr << "summingSeries " << index << " starting" << flush << endl;
    long res = 0;

    if (should_wait)
    {
        std::atomic_fetch_add(&numRunningThreads, 1);
        
        unique_lock<mutex> lock(cvwait_mutex);
        fprintf(stderr, "summingSeries %ld waiting\n", index);
        cv.wait(lock);
        fprintf(stderr, "summingSeries %ld waiting complete, processing\n", index);        
    }
    else
    {
        fprintf(stderr, "summingSeries %ld processing\n", index);

        std::atomic_fetch_add(&numRunningThreads, 1);
        while (numRunningThreads < numTestCases)
            continue;

        // make sure all the waiting threads have started and are
        // waiting on the condition var
        std::this_thread::sleep_for(std::chrono::milliseconds(100));
    }
    
    // auto start = chrono::steady_clock::now();

    // brute force, doesn't work in hacker rank due to 2 second time
    // constraint
    
    // for (long i = 1; i <= n; i++)
    //   {
    //     long x =  powl(i, 2) - powl((i - 1), 2);
    //     res += x;
    //   }

    // auto end = chrono::steady_clock::now();
    // chrono::duration<double> diff = end - start;
    // cerr << "series " << index << " sum time: " << diff.count() << " secs" << endl;

    // refactoring summing series equation yields n^2
    res = (n % MOD) * (n % MOD);    
    
    lock_guard<mutex> guard(result_mutex);
    results[index] = res % MOD;
    
    cv.notify_one();

    fprintf(stderr, "summingSeries %ld complete\n", index);    
}

int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    string t_temp;
    int t;
    if (outputMode == OutputMode::HackerRank)
    {
        getline(cin, t_temp);
        t = stoi(ltrim(rtrim(t_temp)));
    }
    else
    {
        t = 10; // 10 test cases for linux mode tests
    }

    cerr << "test cases: " << t << endl;
    numTestCases = t;

    vector<long> test_inputs1 =
        {229137999, 344936985, 681519110, 494844394,767088309,
         307062702, 306074554, 555026606, 4762607,  231677104};
    
    vector<long> test_inputs2 =
        {5351871996120528,2248813659738258,2494359640703601,6044763399160734,3271269997212342,
         4276346434761561,2372239019637533,5624204919070546,9493965694520825,8629828692375133};
    
    vector<long> test_inputs3 = {1,2,3,4,5,6,7,8,9,10};
    
    thread* threadArr[11];

    for (int t_itr = 0; t_itr < t; t_itr++) {
        string n_temp;
        long n;
        if (outputMode == OutputMode::HackerRank)
        {
            getline(cin, n_temp);
            n = stol(ltrim(rtrim(n_temp)));
        }
        else
        {
            n = test_inputs2[t_itr];
        }

        bool should_wait = t_itr >= maxConcurrentThreads ? true : false; 
    
        threadArr[t_itr] = new thread(summingSeries, n, t_itr, should_wait);
    }

    for (int t_itr = 0; t_itr < t; t_itr++)
        threadArr[t_itr]->join();

    for (int t_itr = 0; t_itr < t; t_itr++)
    {
        cerr << results[t_itr] << endl;
        fout << results[t_itr] << "\n";
    }

    fout.close();

    return 0;
}

std::function<int(int)> f_isspace = [](int x){ return isspace(x); };

string ltrim(const string &str) {
    string s(str);

    s.erase(
        s.begin(),
        find_if(s.begin(), s.end(), not_fn(f_isspace))
        );

    return s;
}

string rtrim(const string &str) {
    string s(str);

    s.erase(
        find_if(s.rbegin(), s.rend(), not_fn(f_isspace)).base(),
        s.end()
        );

    return s;
}