#include <cstdio>
#include <cctype>
using namespace std;

const long long MOD = 666013;


int main()
{
    int t,k; scanf("%d %d",&t,&k);

    long long k_pow=1;
    for(int i=0;i<k;++i){ 
        k_pow<<=1;
        if(k_pow>MOD) k_pow-=MOD;
    }
    long long k1_pow=k_pow*2%MOD;

    int nr_cic=1;
    long long rest[MOD];
    rest[0]=0;

    int nr=k_pow;
    while(nr!=0){
        rest[nr_cic++]=nr;
        nr= (nr*k1_pow + k_pow)%MOD;
    }

    char buff[1000005];
    fgets(buff, 1000005, stdin); // '\n' on the first line...
    char outp[700005];
    int nrout=0;

    for(int i=0;i<t;++i){
        // calculate (huge_nr) modulo (nr_cic)
        int r=0;
        fgets(buff,1000005,stdin); 
               

        for(unsigned j=0;buff[j]!='\0';++j) 
            if(isdigit(buff[j])) r=(r*10+buff[j]-'0')%nr_cic;

        nrout+=sprintf(outp+nrout,"%lld\n",rest[r]);
    }

    outp[nrout-1]='\0';
    puts(outp);
}