#include<stdio.h>
 
#define mod 1000000007
 
long long a[20000010];//函数值
long long b[20000010];//异或和
 
void init()
{
    b[0]=0;
    a[0]=1;
    long long temp5=1;
    int i;
    for(i=1;i<20000005;i++)
    {
        temp5*=500000004;
        temp5%=1000000007;
        a[i]=((a[i-1]*(mod-temp5+1))%mod);
        b[i]=b[i-1]^a[i];
    }
}
 
int main()
{
    init();
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int p;
        scanf("%d",&p);
        printf("%lld\n",b[p]);
    }
}