#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
void solve()
{
    int n;
    cin >> n;
 
    // (a + b) => (a % mod + b % mod) % mod
    // (a - b) => (a % mod - b % mod + mod) % mod
    // (a * b) => ((a % mod) * (b % mod)) % mod
 
    int mod = 1e9 + 7;
 
    int ans = (n % mod);
    ans = (ans * (n + 1)) % mod;
    ans = (ans * (4*n - 1)) % mod;
    ans = (ans * 337) % mod;
 
    cout << ans << endl;
}
 
int32_t main() {
    // your code goes here
    int t;
    cin >> t;
 
    while(t--)
        solve();
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojZGVmaW5lIGludCBsb25nIGxvbmcKCnZvaWQgc29sdmUoKQp7CiAgICBpbnQgbjsKICAgIGNpbiA+PiBuOwogICAgCiAgICAvLyAoYSArIGIpID0+IChhICUgbW9kICsgYiAlIG1vZCkgJSBtb2QKICAgIC8vIChhIC0gYikgPT4gKGEgJSBtb2QgLSBiICUgbW9kICsgbW9kKSAlIG1vZAogICAgLy8gKGEgKiBiKSA9PiAoKGEgJSBtb2QpICogKGIgJSBtb2QpKSAlIG1vZAogICAgCiAgICBpbnQgbW9kID0gMWU5ICsgNzsKICAgIAogICAgaW50IGFucyA9IChuICUgbW9kKTsKICAgIGFucyA9IChhbnMgKiAobiArIDEpKSAlIG1vZDsKICAgIGFucyA9IChhbnMgKiAoNCpuIC0gMSkpICUgbW9kOwogICAgYW5zID0gKGFucyAqIDMzNykgJSBtb2Q7CiAgICAKICAgIGNvdXQgPDwgYW5zIDw8IGVuZGw7Cn0KCmludDMyX3QgbWFpbigpIHsKICAgIC8vIHlvdXIgY29kZSBnb2VzIGhlcmUKICAgIGludCB0OwogICAgY2luID4+IHQ7CiAgICAKICAgIHdoaWxlKHQtLSkKICAgICAgICBzb2x2ZSgpOwp9

NAoyCjMKNTAKMTAwMDAwMDAwMAo=

4
2
3
50
1000000000