stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <bits/stdc++.h>



#define fr first

#define sc second

#define mk make_pair

#define pb push_back

#define sz(s) (int)s.size()

#define all(s) s.begin(), s.end()

#define int long long



using namespace std;



const int N = 25, MASK = 1 << 18, mod = 1e9 + 7;



int n, m, ar[N], dp[N][MASK], fc[MASK], in[MASK], nn, ans;



int binpow (int a, int b)

{

    if (b == 0)

        return 1ll;



    if (b & 1)

        return (a * 1ll * binpow(a, b - 1) % mod);



    int res = binpow(a, b >> 1);



    return (res * 1ll * res % mod);

}

int Calc (int n, int k)

{

    if (n < k)

        return 0ll;



    return fc[n] * 1ll * in[k] % mod * in[n - k] % mod;

}

main()

{

    cin >> n >> m;



    nn = (1 << n);



    fc[0] = in[0] = 1;



    for (int i = 1; i <= nn; i++)

    {

        fc[i] = fc[i - 1] * 1ll * i % mod;

        in[i] = binpow(fc[i], mod - 2);

    }

    for (int i = 1; i <= m; i++)

        cin >> ar[i];



    sort( ar + 1, ar + m + 1, greater <int>() );



    dp[0][0] = 1;



    for (int i = 1; i <= m; i++)

    {



        for (int mask = 0; mask < (1 << n ); mask++)

        {

            int sum = 0;



            for (int j = 0; j < n; j++)

            {

                if (mask & (1 << j))

                    sum += (1 << j);

            }

            dp[i][mask] += dp[i - 1][mask];

            dp[i][mask] %= mod;

            for (int j = 0; j < n; j++)

            {

                if (!(mask & (1 << j)) ) continue;



                dp[i][mask] += ( (dp[i - 1][mask ^ (1 << j) ] * 1ll * fc[ (1 << j) ] ) % mod * 1LL * Calc( nn - ar[i] - sum + (1 << j), (1 << j) - 1 ) ) % mod;

                dp[i][mask] %= mod;

            }

        }

    }

    for (int mask = 0; mask < (1 << n); mask++)

    {

        int res = dp[m][mask], sum = 0;



        if (__builtin_popcount(mask) & 1)

            res = -res + mod;



        for (int i = 0; i < n; i++)

        {

            if (mask & (1 << i)) continue;

            sum += (1 << i);

        }



        ans = ans + res * fc[sum] % mod;



        ans %= mod;

    }

    cout << ans * (1 << n) % mod << endl;

}


// Faster C++ solution for the same problem (measured speedup: 5.072082065454463x):
#include<cstdio>

#include<algorithm>

#include<cstring>

typedef long long ll;

using namespace std;

int n,m,i,a[18];

ll F[1<<17],inv[1<<17],f[1<<17],ans;

const int mod=1e9+7;

int C(int a,int b){return a<b?0:F[a]*inv[b]%mod*inv[a-b]%mod;}

void dec(ll &a,int b){(a-=b)<0?a+=mod:0;}

void inc(ll &a,int b){(a+=b)>=mod?a-=mod:0;}

int main(){

	scanf("%d%d",&n,&m);F[0]=F[1]=inv[0]=inv[1]=1;

	for(i=2;i<=(1<<n);i++)F[i]=F[i-1]*i%mod,inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;

	for(i=2;i<=(1<<n);i++)inv[i]=inv[i]*inv[i-1]%mod;

	for(i=1;i<=m;i++)scanf("%d",&a[i]);

	for(f[0]=1<<n,i=m;i;i--)for(int j=(1<<n)-1;j;j--)for(int k=0;k<n;k++)if(j&(1<<k))dec(f[j],f[j^(1<<k)]*C((1<<n)-a[i]-(j^(1<<k)),(1<<k)-1)%mod*F[1<<k]%mod);

	for(i=0;i<(1<<n);i++)inc(ans,f[i]*F[(1<<n)-i-1]%mod);

	printf("%lld\n",ans);

}
// Slower C++ solution:
#include<cstdio>

#include<algorithm>

#include<cstring>

typedef long long ll;

using namespace std;

int n,m,i,a[18];

ll F[1<<17],inv[1<<17],f[1<<17],ans;

const int mod=1e9+7;

int C(int a,int b){return a<b?0:F[a]*inv[b]%mod*inv[a-b]%mod;}

void dec(ll &a,int b){(a-=b)<0?a+=mod:0;}

void inc(ll &a,int b){(a+=b)>=mod?a-=mod:0;}

int main(){

	scanf("%d%d",&n,&m);F[0]=F[1]=inv[0]=inv[1]=1;

	for(i=2;i<=(1<<n);i++)F[i]=F[i-1]*i%mod,inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;

	for(i=2;i<=(1<<n);i++)inv[i]=inv[i]*inv[i-1]%mod;

	for(i=1;i<=m;i++)scanf("%d",&a[i]);

	for(f[0]=1<<n,i=m;i;i--)for(int j=(1<<n)-1;j;j--)for(int k=0;k<n;k++)if(j&(1<<k))dec(f[j],f[j^(1<<k)]*C((1<<n)-a[i]-(j^(1<<k)),(1<<k)-1)%mod*F[1<<k]%mod);

	for(i=0;i<(1<<n);i++)inc(ans,f[i]*F[(1<<n)-i-1]%mod);

	printf("%lld\n",ans);

}




// Faster C++ solution for the same problem (measured speedup: 1.6594997682416222x):
#include <cstdio>

#include <algorithm>

#include <vector>

#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)



inline int read()

{

	int data = 0, w = 1; char ch = getchar();

	while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();

	if (ch == '-') w = -1, ch = getchar();

	while (ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = getchar();

	return data * w;

}



const int N(18), maxn(1 << 17), Mod(1e9 + 7);

inline void Add(int &x, int y) { x = (x + y) % Mod; }

int bin[N], fac[maxn], inv[maxn], n, m, ans, f[N][maxn], cnt[maxn], A[N];

inline int C(int n, int m) { return n < m ? 0 : 1ll * fac[n] * inv[m] % Mod * inv[n - m] % Mod; }

int fastpow(int x, int y)

{

	int ans = 1;

	for (; y; y >>= 1, x = 1ll * x * x % Mod)

		if (y & 1) ans = 1ll * ans * x % Mod;

	return ans;

}



int main()

{

	n = read(), m = read(), cnt[0] = bin[0] = fac[0] = inv[0] = 1;

	for (int i = 1; i <= n; i++) bin[i] = bin[i - 1] << 1;

	for (int i = 1; i <= bin[n]; i++) fac[i] = 1ll * fac[i - 1] * i % Mod;

	inv[bin[n]] = fastpow(fac[bin[n]], Mod - 2);

	for (int i = bin[n] - 1; i; i--) inv[i] = 1ll * inv[i + 1] * (i + 1) % Mod;

	for (int i = 1; i <= bin[n]; i++) cnt[i] = (i & 1) ? Mod - cnt[i >> 1] : cnt[i >> 1];

	for (int i = 1; i <= m; i++) A[i] = read(); std::sort(A + 1, A + m + 1);

	f[m + 1][0] = 1;

	for (int i = m; i; i--) for (int S = 0; S < bin[n]; S++) if (f[i + 1][S])

	{

		Add(f[i][S], f[i + 1][S]); int t = (bin[n] - 1) ^ S;

		for (int j = 0; j < n; j++) if (!(S & bin[j]))

			Add(f[i][S | bin[j]], 1ll * C(t - A[i] + 1, bin[j] - 1) *

					f[i + 1][S] % Mod * fac[bin[j]] % Mod);

	}

	for (int i = 0; i < bin[n]; i++)

		Add(ans, 1ll * f[1][i] * fac[bin[n] - 1 - i] % Mod * cnt[i] % Mod);

	ans = 1ll * ans * bin[n] % Mod; printf("%d\n", ans);

	return 0;

}
// Slower C++ solution:
#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

const int N=16;

const int MOD=1e9+7;

int n,m;

int a[N+1];

long long f[N+1][1<<N|1],fac[1<<N|1],inv[1<<N|1];

long long ksm(long long a,long long b)

{

	long long res=1;

	while(b)

	{

		if(b&1) res=res*a%MOD;

		a=a*a%MOD,b>>=1;

	}

	return res;

}

long long C(int n,int m)

{

    if(n<m) return 0;

    return fac[n]*inv[m]%MOD*inv[n-m]%MOD;

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=1;i<=m;i++)

		scanf("%d",&a[i]);

    fac[0]=1;

    for(int i=1;i<=(1<<n);i++)

		fac[i]=fac[i-1]*i%MOD;

	inv[1<<n]=ksm(fac[1<<n],MOD-2);

    for(int i=1<<n;i>=1;i--)

    	inv[i-1]=inv[i]*i%MOD;

    sort(a+1,a+m+1,greater<int>());

    f[0][0]=1;

    for(int i=1;i<=m;i++)

        for(int j=0;j<(1<<n);j++)

		{

            f[i][j]=(f[i][j]+f[i-1][j])%MOD;

            for(int k=0;k<n;k++)

			{

                if(j&(1<<k)) continue;

                if((1<<n)-j-a[i]<(1<<k)-1) break;

                f[i][j|(1<<k)]=(f[i][j|(1<<k)]-f[i-1][j]*C((1<<n)-j-a[i],(1<<k)-1)%MOD*fac[1<<k]%MOD+MOD)%MOD;

            }

        }

    long long ans=0;

    for(int i=0;i<(1<<n);i++)

        ans=(f[m][i]*fac[(1<<n)-i-1]%MOD+ans)%MOD;

    ans=(ans*(1<<n)%MOD)%MOD;

    printf("%lld",ans);

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.106533544313527x):
#include <cstdio>



const int MAXN = (1<<16);

const int MOD = int(1E9) + 7;



int pow_mod(int b, int p) {

	int ret = 1;

	while( p ) {

		if( p & 1 ) ret = 1LL*ret*b%MOD;

		b = 1LL*b*b%MOD;

		p >>= 1;

	}

	return ret;

}



int fct[MAXN + 5], ifct[MAXN + 5];

void init() {

	fct[0] = 1;

	for(int i=1;i<=MAXN;i++)

		fct[i] = 1LL*fct[i-1]*i%MOD;

	ifct[MAXN] = pow_mod(fct[MAXN], MOD - 2);

	for(int i=MAXN-1;i>=0;i--)

		ifct[i] = 1LL*ifct[i+1]*(i+1)%MOD;

}

int comb(int n, int m) {

	return 1LL*fct[n]*ifct[m]%MOD*ifct[n-m]%MOD;

}



int f[MAXN + 5], dp[MAXN + 5];

int lowbit(int x) {

	return x & -x;

}



int A[16], N, M, t;

int main() {

	init();

	scanf("%d%d", &N, &M), t = (1 << N);

	for(int i=0;i<M;i++)

		scanf("%d", &A[i]);

	dp[0] = f[0] = 1;

	for(int i=1;i<t;i++)

		f[i] = 1LL*comb(i, lowbit(i))*f[i^lowbit(i)]%MOD;

	for(int i=M-1;i>=0;i--) {

		for(int s=t-1;s>=0;s--) {

			int p = (t - A[i]) - s;

			for(int j=0;j<N;j++) {

				int q = (1 << j);

				if( !(s & q) && p >= q - 1 )

					dp[s|q] = (dp[s|q] + MOD - 1LL*dp[s]*comb(p,q-1)%MOD) % MOD;

			}

		}

	}

	int ans = 0;

	for(int i=0;i<t;i++) ans = (ans + 1LL*dp[i]*f[t-1-i]%MOD) % MOD;

	for(int i=0;i<N;i++) ans = 1LL*ans*fct[1 << i] % MOD;

	printf("%lld\n", 1LL*ans*t%MOD);

}
// Slower C++ solution:
#include <iostream>

#include <algorithm>

#include <iomanip>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <math.h>

#include <vector>

#include <string>

#include <queue>

#include <deque>

#include <list>

#include <set>

#include <unordered_set>

#include <map>

#include <unordered_map>

#include <bitset>

#include <random>

#include <complex>

#include <assert.h>



using namespace std;

typedef long long ll;

#define endl '\n'



/////////////         modの計算



#define MOD_IS_PRIME

constexpr ll mod = 1000000007LL;



int main() {

	ios::sync_with_stdio(false);

	std::cin.tie(0);



	constexpr int K = 16;



	vector<ll> v_e = { 0, 765144583, 346175634, 347662323, 5655049, 184117322, 927321758, 444014759, 542573865, 237315285, 417297686, 471090892, 183023413, 660103155, 727008098, 869418286 };

	vector<ll> v_o = { 539588932, 729548371, 700407153, 404391958, 962779130, 184117322, 927321758, 444014759, 542573865, 237315285, 417297686, 471090892, 183023413, 660103155, 727008098, 869418286 };



	int T; cin >> T;

	for (int _t = 0; _t < T; _t++) {

		ll N; cin >> N;

		if (N % 2 == 0) {// even

			ll ans = 0;

			ll x = 1;

			for (int i = 0; i < K; i++) {

				ans += (x * v_e[i]) % mod;

				x = (x * N) % mod;

			}

			cout << ans % mod << endl;

		}

		else {// odd

			ll ans = 0;

			ll x = 1;

			for (int i = 0; i < K; i++) {

				ans += (x * v_o[i]) % mod;

				x = (x * N) % mod;

			}

			cout << ans % mod << endl;

		}

	}



	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.297807827529027x):
#include <stdio.h>



typedef long long ll;



/////////////         modの計算

const ll mod = 1000000007LL;



class modlong {

public:

	modlong() { x = 0; }

	modlong(ll num) { x = num; }

	inline operator ll() const { return x; }

	inline void operator = (ll num) { x = num; }

	inline void operator += (ll num) { x = adjust(x + num); }

	inline void operator *= (ll num) { x = adjust(x * num); }

	inline modlong operator * (ll num) { modlong m(adjust(this->x * num)); return m; }

private:

	inline ll adjust(ll a) {

		if (a >= mod) { return a % mod; }

		return a;

	}

	ll x;

};



constexpr int K = 16;



constexpr ll v_e[] = { 0, 765144583, 346175634, 347662323, 5655049, 184117322, 927321758, 444014759, 542573865, 237315285, 417297686, 471090892, 183023413, 660103155, 727008098, 869418286 };

constexpr ll v_o[] = { 539588932, 729548371, 700407153, 404391958, 962779130, 184117322, 927321758, 444014759, 542573865, 237315285, 417297686, 471090892, 183023413, 660103155, 727008098, 869418286 };



int main() {

	int T; scanf("%d", &T);

	for (int _t = 0; _t < T; _t++) {

		ll N; scanf("%ld", &N);

		modlong ans = 0;

		modlong x = 1;



		if (N & 1) {// odd

			for (int i = 0; i < K; i++) {

				ans += x * v_o[i];

				x *= N;

			}

		}

		else {// even

			for (int i = 0; i < K; i++) {

				ans += x * v_e[i];

				x *= N;

			}

		}

		printf("%ld\n", ans);

	}



	return 0;

}
// Slower C++ solution:
#include <iostream>

#include <algorithm>

#include <iomanip>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <math.h>

#include <vector>

#include <string>

#include <queue>

#include <deque>

#include <list>

#include <set>

#include <unordered_set>

#include <map>

#include <unordered_map>

#include <bitset>

#include <random>

#include <complex>

#include <assert.h>



using namespace std;

typedef long long ll;

#define endl '\n'



/////////////         modの計算



#define MOD_IS_PRIME

constexpr ll mod = 1000000007LL;



int main() {

	ios::sync_with_stdio(false);

	std::cin.tie(0);



	constexpr int K = 16;



	vector<ll> v_e = { 0, 765144583, 346175634, 347662323, 5655049, 184117322, 927321758, 444014759, 542573865, 237315285, 417297686, 471090892, 183023413, 660103155, 727008098, 869418286 };

	vector<ll> v_o = { 539588932, 729548371, 700407153, 404391958, 962779130, 184117322, 927321758, 444014759, 542573865, 237315285, 417297686, 471090892, 183023413, 660103155, 727008098, 869418286 };



	int T; cin >> T;

	for (int _t = 0; _t < T; _t++) {

		ll N; cin >> N;

		if (N % 2 == 0) {// even

			ll ans = 0;

			ll x = 1;

			for (int i = 0; i < K; i++) {

				ans += x * v_e[i];

				x *= N;

				if (ans >= mod) { ans %= mod; }

				if (x >= mod) { x %= mod; }

			}

			cout << ans << endl;

		}

		else {// odd

			ll ans = 0;

			ll x = 1;

			for (int i = 0; i < K; i++) {

				ans += x * v_o[i];

				x *= N;

				if (ans >= mod) { ans %= mod; }

				if (x >= mod) { x %= mod; }

			}

			cout << ans << endl;

		}

	}



	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.302224562796372x):
#include <stdio.h>



typedef long long ll;



/////////////         modの計算

const ll mod = 1000000007LL;



class modlong {

public:

	modlong() { x = 0; }

	modlong(ll num) { x = num; }

	inline operator ll() const { return x; }

	inline void operator = (ll num) { x = num; }

	inline void operator += (ll num) { x = adjust(x + num); }

	inline void operator *= (ll num) { x = adjust(x * num); }

	inline modlong operator * (ll num) { modlong m(adjust(this->x * num)); return m; }

private:

	inline ll adjust(ll a) {

		if (a >= mod) { return a % mod; }

		return a;

	}

	ll x;

};



constexpr int K = 16;



constexpr ll v_e[] = { 0, 765144583, 346175634, 347662323, 5655049, 184117322, 927321758, 444014759, 542573865, 237315285, 417297686, 471090892, 183023413, 660103155, 727008098, 869418286 };

constexpr ll v_o[] = { 539588932, 729548371, 700407153, 404391958, 962779130, 184117322, 927321758, 444014759, 542573865, 237315285, 417297686, 471090892, 183023413, 660103155, 727008098, 869418286 };



int main() {

	int T; scanf("%d", &T);

	for (int _t = 0; _t < T; _t++) {

		ll N; scanf("%ld", &N);

		modlong ans = 0;

		modlong x = 1;



		if (N & 1) {// odd

			for (int i = 0; i < K; i++) {

				ans += x * v_o[i];

				x *= N;

			}

		}

		else {// even

			for (int i = 0; i < K; i++) {

				ans += x * v_e[i];

				x *= N;

			}

		}

		printf("%ld\n", ans);

	}



	return 0;

}
// Slower C++ solution:
#include <iostream>

#include <algorithm>

#include <iomanip>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <math.h>

#include <vector>

#include <string>

#include <queue>

#include <deque>

#include <list>

#include <set>

#include <unordered_set>

#include <map>

#include <unordered_map>

#include <bitset>

#include <random>

#include <complex>

#include <assert.h>



using namespace std;

typedef long long ll;



constexpr ll mod = 1000000007;

constexpr ll v[] = { 0, 765144583, 346175634, 347662323, 5655049, 184117322, 927321758, 444014759, 542573865, 237315285, 417297686, 471090892, 183023413, 660103155, 727008098, 539588932, 729548371, 700407153, 404391958, 962779130, 184117322, 927321758, 444014759, 542573865, 237315285, 417297686, 471090892, 183023413, 660103155, 727008098 };



int main() {

	int N, T; scanf("%d", &T);

	for (int _t = 0; _t < T; _t++) {

		scanf("%d", &N);

		ll ans = 869418286;

		if (N & 1) {// odd

			for (int i = 14, j = 29; i >= 0; i--, j--) {

				ans = (ans * N + v[j]) % mod;

			}

		}

		else {// even

			for (int i = 14; i >= 0; i--) {

				ans = (ans * N + v[i]) % mod;

			}

		}

		printf("%d\n", ans);

	}



	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.112391430817096x):
#include <stdio.h>



typedef long long ll;



/////////////         modの計算

const ll mod = 1000000007LL;



class modlong {

public:

	modlong() { x = 0; }

	modlong(ll num) { x = num; }

	inline operator ll() const { return x; }

	inline void operator = (ll num) { x = num; }

	inline void operator += (ll num) { x = adjust(x + num); }

	inline void operator *= (ll num) { x = adjust(x * num); }

	inline modlong operator * (ll num) { modlong m(adjust(this->x * num)); return m; }

private:

	inline ll adjust(ll a) {

		if (a >= mod) { return a % mod; }

		return a;

	}

	ll x;

};



constexpr int K = 16;



constexpr ll v_e[] = { 0, 765144583, 346175634, 347662323, 5655049, 184117322, 927321758, 444014759, 542573865, 237315285, 417297686, 471090892, 183023413, 660103155, 727008098, 869418286 };

constexpr ll v_o[] = { 539588932, 729548371, 700407153, 404391958, 962779130, 184117322, 927321758, 444014759, 542573865, 237315285, 417297686, 471090892, 183023413, 660103155, 727008098, 869418286 };



int main() {

	int T; scanf("%d", &T);

	for (int _t = 0; _t < T; _t++) {

		ll N; scanf("%ld", &N);

		modlong ans = 0;

		modlong x = 1;



		if (N & 1) {// odd

			for (int i = 0; i < K; i++) {

				ans += x * v_o[i];

				x *= N;

			}

		}

		else {// even

			for (int i = 0; i < K; i++) {

				ans += x * v_e[i];

				x *= N;

			}

		}

		printf("%ld\n", ans);

	}



	return 0;

}
// Slower C++ solution:
#include <iostream>

#include <algorithm>

#include <iomanip>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <math.h>

#include <vector>

#include <string>

#include <queue>

#include <deque>

#include <list>

#include <set>

#include <unordered_set>

#include <map>

#include <unordered_map>

#include <bitset>

#include <random>

#include <complex>

#include <assert.h>



using namespace std;

typedef long long ll;

#define endl '\n'



const ll mod = 1000000007LL;



int main() {

	ios::sync_with_stdio(false);

	std::cin.tie(0);



	constexpr int K = 16;



	constexpr ll v_e[] = { 869418286, 727008098, 660103155, 183023413, 471090892, 417297686, 237315285, 542573865, 444014759, 927321758, 184117322, 5655049, 347662323, 346175634, 765144583, 0};

	constexpr ll v_o[] = { 869418286, 727008098, 660103155, 183023413, 471090892, 417297686, 237315285, 542573865, 444014759, 927321758, 184117322, 962779130, 404391958, 700407153, 729548371, 539588932 };



	ll T, N; cin >> T;

	for (int _t = 0; _t < T; _t++) {

		cin >> N;

		ll ans = v_e[0];

		if (N & 1) {// odd

			for (int i = 1; i < K; i++) {

				ans *= N;

				ans += v_o[i];

				ans %= mod;

			}

		}

		else {// even

			for (int i = 1; i < K; i++) {

				ans *= N;

				ans += v_e[i];

				ans %= mod;

			}

		}

		cout << ans << endl;

	}



	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.235394971463504x):
#include <stdio.h>



typedef long long ll;



/////////////         modの計算

const ll mod = 1000000007LL;



class modlong {

public:

	modlong() { x = 0; }

	modlong(ll num) { x = num; }

	inline operator ll() const { return x; }

	inline void operator = (ll num) { x = num; }

	inline void operator += (ll num) { x = adjust(x + num); }

	inline void operator *= (ll num) { x = adjust(x * num); }

	inline modlong operator * (ll num) { modlong m(adjust(this->x * num)); return m; }

private:

	inline ll adjust(ll a) {

		if (a >= mod) { return a % mod; }

		return a;

	}

	ll x;

};



constexpr int K = 16;



constexpr ll v_e[] = { 0, 765144583, 346175634, 347662323, 5655049, 184117322, 927321758, 444014759, 542573865, 237315285, 417297686, 471090892, 183023413, 660103155, 727008098, 869418286 };

constexpr ll v_o[] = { 539588932, 729548371, 700407153, 404391958, 962779130, 184117322, 927321758, 444014759, 542573865, 237315285, 417297686, 471090892, 183023413, 660103155, 727008098, 869418286 };



int main() {

	int T; scanf("%d", &T);

	for (int _t = 0; _t < T; _t++) {

		ll N; scanf("%ld", &N);

		modlong ans = 0;

		modlong x = 1;



		if (N & 1) {// odd

			for (int i = 0; i < K; i++) {

				ans += x * v_o[i];

				x *= N;

			}

		}

		else {// even

			for (int i = 0; i < K; i++) {

				ans += x * v_e[i];

				x *= N;

			}

		}

		printf("%ld\n", ans);

	}



	return 0;

}
// Slower C++ solution:
#include <iostream>

#include <algorithm>

#include <iomanip>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <math.h>

#include <vector>

#include <string>

#include <queue>

#include <deque>

#include <list>

#include <set>

#include <unordered_set>

#include <map>

#include <unordered_map>

#include <bitset>

#include <random>

#include <complex>

#include <assert.h>



using namespace std;

typedef long long ll;

#define endl '\n'



const ll mod = 1000000007LL;



int main() {

	ios::sync_with_stdio(false);

	std::cin.tie(0);



	constexpr int K = 16;



	constexpr ll v_e[] = { 869418286, 727008098, 660103155, 183023413, 471090892, 417297686, 237315285, 542573865, 444014759, 927321758, 184117322, 5655049, 347662323, 346175634, 765144583, 0};

	constexpr ll v_o[] = { 869418286, 727008098, 660103155, 183023413, 471090892, 417297686, 237315285, 542573865, 444014759, 927321758, 184117322, 962779130, 404391958, 700407153, 729548371, 539588932 };



	ll T, N; cin >> T;

	for (int _t = 0; _t < T; _t++) {

		cin >> N;

		ll ans = v_e[0];

		if (N & 1) {// odd

			for (int i = 1; i < K; i++) {

				ans = ans * N + v_o[i];

				if(ans >= mod) ans %= mod;

			}

		}

		else {// even

			for (int i = 1; i < K; i++) {

				ans = ans * N + v_e[i];

				if (ans >= mod) ans %= mod;

			}

		}

		cout << ans << endl;

	}



	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.236329541676755x):
#include <stdio.h>



typedef long long ll;



/////////////         modの計算

const ll mod = 1000000007LL;



class modlong {

public:

	modlong() { x = 0; }

	modlong(ll num) { x = num; }

	inline operator ll() const { return x; }

	inline void operator = (ll num) { x = num; }

	inline void operator += (ll num) { x = adjust(x + num); }

	inline void operator *= (ll num) { x = adjust(x * num); }

	inline modlong operator * (ll num) { modlong m(adjust(this->x * num)); return m; }

private:

	inline ll adjust(ll a) {

		if (a >= mod) { return a % mod; }

		return a;

	}

	ll x;

};



constexpr int K = 16;



constexpr ll v_e[] = { 0, 765144583, 346175634, 347662323, 5655049, 184117322, 927321758, 444014759, 542573865, 237315285, 417297686, 471090892, 183023413, 660103155, 727008098, 869418286 };

constexpr ll v_o[] = { 539588932, 729548371, 700407153, 404391958, 962779130, 184117322, 927321758, 444014759, 542573865, 237315285, 417297686, 471090892, 183023413, 660103155, 727008098, 869418286 };



int main() {

	int T; scanf("%d", &T);

	for (int _t = 0; _t < T; _t++) {

		ll N; scanf("%ld", &N);

		modlong ans = 0;

		modlong x = 1;



		if (N & 1) {// odd

			for (int i = 0; i < K; i++) {

				ans += x * v_o[i];

				x *= N;

			}

		}

		else {// even

			for (int i = 0; i < K; i++) {

				ans += x * v_e[i];

				x *= N;

			}

		}

		printf("%ld\n", ans);

	}



	return 0;

}