#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
const int N = 1000500;
const int Mod = 1000000007;
int n,m;
int getint()
{
    int res=0;
    char ch=getchar();
    while((ch<'0' || ch>'9') && ch!='-')
        ch=getchar();
    bool fan=0;
    if(ch=='-')
    {
        fan=1;
        ch=getchar();
    }
    while('0'<=ch && ch<='9')
    {
        res=res*10+ch-'0';
        ch=getchar();
    }
    if(fan)
        res=-res;
    return res;
}
int c(int x,int y)
{
    long long z=x;
    z*=y;
    z%=Mod;
    x=z;
    return x;
}
int f()
{
    m=getint();
    if(m%2==0)
    {
        int t=(n-m/2)/m;
        int add=m-(n-m/2)%m;
        int start=t-m/2+1;
        if(start<1)
            return -1;
        int i;
        int res=1;
        for(i=0;i<m;i++)
        {
            if(i<add)
                res=c(res,start+i);
            else
                res=c(res,start+i+1);
        }
        return res;
    }
    else
    {
        int t=n/m;
        int add=m-n%m;
        int start=t-m/2;
        if(start<1)
            return -1;
        int i;
        int res=1;
        for(i=0;i<m;i++)
        {
            if(i<add)
                res=c(res,start+i);
            else
                res=c(res,start+i+1);
        }
        return res;
    }
}
int main()
{
    int T=getint();
    while((scanf("%d",&n))!=EOF)
        printf("%d\n",f());
    return 0;
}