/* in the name of god */ //#pragma GCC optimize("Ofast,O3,unroll-loops") //#pragma GCC target("avx,avx2,fma") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,sse4a,avx,avx2,popcnt,tune=native") #include <bits/stdc++.h> using namespace std; #define int long long typedef pair<int,int> pii; typedef pair<long long ,long long> pll; typedef long long ll ; #define File freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #define all(V) V.begin(),V.end() #define setprec(x) fixed << setprecision(x) #define Mp(a,b) make_pair(a,b) #define len(V) (int)(V.size()) #define sep ' ' // #define endl '\n' #define pb push_back #define fi first #define sec second #define popcount(x) __builtin_popcount(x) #define lid u<<1 #define rid (lid)|1 mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); const ll N = 2e5 + 10,SQ=320,LOG=62; const ll inf = 2e9 , MD = 1e9 + 7; inline ll md(ll x){ x %= MD; return (x < 0 ? x + MD : x);} int dp[LOG][LOG][2*LOG]; int sz[LOG]; int f[LOG][2*LOG]; int dp2[LOG][2*LOG]; int num[LOG][LOG]; ll big_pow(ll n ,ll x,ll md = MD){ ll ans = 1; x %= (MD-1); while(x){ if(x&1) ans = (1LL*ans*n)%md; n = (1LL*n*n)%md; x /= 2; } return ans; } inline ll divide(ll p , ll q,ll MOD = MD){ return ((p%MOD) * big_pow(q,MOD-2,MOD))%MOD; } vector<int> pt; void Divide(int n){ if(n == 0) assert(0); if(n == 1) return; int lg=0; for(int i = 1 ;i <LOG;i++){ if(sz[i] <= n) lg = i; } int tt = n - sz[lg]; if((1LL<<(lg-1)) >= tt) { pt.pb(lg-1); Divide(n - sz[lg-1] - 1); } else { pt.pb(lg); Divide(n - sz[lg]-1); } } int pre[LOG][2*LOG],suf[LOG][2*LOG]; int solve(int n){ int lg= 0; for(int i =1 ;i < LOG;i++){ if(sz[i] <= n) lg =i; } if(sz[lg] == n){ int ans = 0; for(int j =0 ; j < 2*LOG;j++) ans = md(ans + f[lg][j]); ans = md(ans - md(md(n) * (2 * LOG - 1))); return divide(ans,md(big_pow(2,n) - 1)); } pt.clear(); int ans = md(md(n) * (2*LOG - 1)); ans = md(-ans); Divide(n); pt.pb(0); int ln = len(pt); pt.insert(pt.begin(),-1); for(int j = 0;j < 2*LOG;j++) pre[0][j] = 1; int tit = 0; for(int i = 1;i <= ln;i++){ tit += 1 + sz[pt[i]]; pre[i][0] = big_pow(2,tit); for(int j = 1; j < 2*LOG;j++){ pre[i][j] = md(pre[i-1][j-1] * dp2[pt[i]][j-1]); } } for(int j = 0 ;j < 2*LOG;j++) suf[ln+1][j] = 1; tit = 0; for(int i = ln;i >= 1;i--){ tit += 1 + sz[pt[i]]; suf[i][0] = big_pow(2,tit); for(int j = 1; j < 2*LOG;j++){ suf[i][j] = md(suf[i+1][j-1] * md(dp2[pt[i]][j-1])); } } for(int i =1 ;i <= ln;i++){ for(int j =1 ;j < 2*LOG;j++){ ans = md(ans + md(pre[i][j] * suf[i+1][j-1])); } } for(int i =1;i <= ln;i++){ if(pt[i] == 0) continue; for(int j = 0 ; j < 2*LOG;j++){ int tmp = f[pt[i]][j]; if(max(0LL,j-1) == 0) tmp = md(tmp * 2); int k = max(0LL,j-1); tmp = md(tmp * pre[i-1][max(0LL,k-1)]); tmp = md(tmp * suf[i+1][max(0LL,k-1)]); ans = md(ans + tmp); } } ans = divide(ans,md(big_pow(2,n) - 1)); return ans; } int32_t main() { ios_base::sync_with_stdio(false);cout.tie(0);cin.tie(0); for(int j =1;j<2*LOG;j++) dp[1][1][j] = 1; dp[1][1][0] = 2; sz[1] = 1; for(int i = 2;i < LOG;i++){ sz[i] = 2*sz[i-1] + 1; dp[i][1][0] = big_pow(2,sz[i]); for(int j = 1; j < 2*LOG;j++){ dp[i][1][j] = md(dp[i-1][1][j-1] * dp[i-1][1][j-1]); } for(int r = 2; r <= i;r++){ for(int j = 0;j < 2*LOG;j++){ if(j <= r-1) dp[i][r][j] = md(dp[i-1][r-1][j] * big_pow(2,sz[i-1] + 1)); else { dp[i][r][j] = md(dp[i-1][r-1][j] * dp[i-1][1][j - (r - 1) - 1]); } } } } fill(dp2[0],dp2[0]+2*LOG,1); for(int i = 1 ;i < LOG;i++){ for(int j =0 ;j < 2*LOG;j++){ int rem; if(j <= i) rem = sz[i] - sz[j]; else rem = 0; dp2[i][j] = big_pow(2,rem); } } for(int i = 1;i < LOG;i++){ for(int j = 1;j <= i;j++) num[i][j] = big_pow(2,j-1); } for(int i = 1;i < LOG;i++){ for(int r =1;r <= i;r++){ for(int j = 1; j < 2*LOG;j++){ f[i][max(0LL,j - (r-1))] = md(f[i][max(0LL,j - (r-1))] + md(num[i][r] * dp[i][r][j])); } } } int q; cin >> q; while(q--){ int n; cin >> n; pt.clear(); cout << solve(n) << endl; } return 0; }