#include <iostream>
int mod, t, k, x, nr, p, i;
using namespace std;
int ridica_putere(int n, int k)
{
    long long y;
    if(k==0)
        return 1;
    else
        if(k%2==0)
        {
            y=ridica_putere(n,k/2);
            return ((y%mod)*(y%mod))%mod;
        }
        else
        {
            y=ridica_putere(n,k/2);
            return ((((y%mod)*(y%mod))%mod)*n)%mod;
        }
}
int main()
{
    mod=666013;
    cin>>t>>k;
    for(i=1;i<=t;++i)
    {
        cin>>x;
        nr=0;
        for(p=k;p<=x*(k+1);p+=k+1)
        {
            nr=nr+ridica_putere(2,p);
            nr=nr%mod;
        }
        cout<<nr<<endl;
    }
    return 0;
}