#include <iostream>
using namespace std;

const int MOD = 666013;


int main()
{
    cin.sync_with_stdio(false);
    cout.sync_with_stdio(false);

    int t,k; 
    cin>>t>>k;

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

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

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

    int nrout=0;
    int outp[100000];

    char buff[1000005];
    cin.ignore(100,'\n'); 

    for(int i=0;i<t;++i){
        // calculate (huge_nr) modulo (nr_cic)
        int r=0;
        cin.get(buff,1000005,'\n'); 
        cin.get();       

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

        outp[nrout++]=rest[r];
    }

    for(int i=0;i<nrout;++i) cout<<outp[i]<<'\n';
}