Given is an integer N. Snuke will choose integers s_1, s_2, n_1, n_2, u_1, u_2, k_1, k_2, e_1, and e_2 so that all of the following six conditions will be satisfied:

* 0 \leq s_1 < s_2
* 0 \leq n_1 < n_2
* 0 \leq u_1 < u_2
* 0 \leq k_1 < k_2
* 0 \leq e_1 < e_2
* s_1 + s_2 + n_1 + n_2 + u_1 + u_2 + k_1 + k_2 + e_1 + e_2 \leq N



For every possible choice (s_1,s_2,n_1,n_2,u_1,u_2,k_1,k_2,e_1,e_2), compute (s_2 − s_1)(n_2 − n_1)(u_2 − u_1)(k_2 - k_1)(e_2 - e_1), and find the sum of all computed values, modulo (10^{9} +7).

Solve this problem for each of the T test cases given.

Constraints

* All values in input are integers.
* 1 \leq T \leq 100
* 1 \leq N \leq 10^{9}

Input

Input is given from Standard Input in the following format:


T
\mathrm{case}_1
\vdots
\mathrm{case}_T


Each case is given in the following format:


N


Output

Print T lines. The i-th line should contain the answer to the i-th test case.

Example

Input

4
4
6
10
1000000000


Output

0
11
4598
257255556
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
const ll MOD=1e9+7;
ll c1[]={539588932,729548371,700407153,404391958,962779130,184117322,927321758,444014759,542573865,237315285,417297686,471090892,183023413,660103155,727008098,869418286};
ll c0[]={0,765144583,346175634,347662323,5655049,184117322,927321758,444014759,542573865,237315285,417297686,471090892,183023413,660103155,727008098,869418286};
/*int solve(int n){
	ll ans=0;
	for(int s1=0; s1<=n; s1++){
		for(int s2=s1+1; s2+s1<=n; s2++){
			for(int n1=0; n1+s2+s1<=n; n1++){
				for(int n2=n1+1; n2+n1+s2+s1<=n; n2++){
					for(int u1=0; u1+n2+n1+s2+s1<=n; u1++){
						for(int u2=u1+1; u2+u1+n2+n1+s2+s1<=n; u2++){
							for(int k1=0; k1+u2+u1+n2+n1+s2+s1<=n; k1++){
								for(int k2=k1+1; k2+k1+u2+u1+n2+n1+s2+s1<=n; k2++){
									for(int e1=0; e1+k2+k1+u2+u1+n2+n1+s2+s1<=n; e1++){
										for(int e2=e1+1; e2+e1+k2+k1+u2+u1+n2+n1+s2+s1<=n; e2++){
											ans+=(s2-s1)*(n2-n1)*(u2-u1)*(k2-k1)*(e2-e1);
											ans%=MOD;
										}
									}
								}
							}
						}
					}
				}
			}
		}
	}
	return ans;
}*/
int main()
{
	int t; cin>>t;
	while(t--){
		ll n; cin>>n;
		if(n%2==0){
			ll ans=0;
			ll p=1;
			for(int i=0; i<16; i++){
				(ans+=c0[i]*p)%=MOD;
				(p*=n)%=MOD;
			}
			cout<<ans<<endl;
		}else{
			ll ans=0;
			ll p=1;
			for(int i=0; i<16; i++){
				(ans+=c1[i]*p)%=MOD;
				(p*=n)%=MOD;
			}
			cout<<ans<<endl;
		}
	}
	return 0;
}