#include<stdio.h>
#include<algorithm>
#include<vector>
#include<cstring>
#include<map>

#define mod 666013
#define inf (1<<30)
#define maxdim 1000005

using namespace std;

int k,tests;
int in[mod+5];
char sir[maxdim];
vector<int>V;

int main () {
	
	#ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	#endif
	
	scanf("%d %d\n",&tests,&k);
	
	int p2k = 1,pp = 1;
	for ( int i = 1 ; i <= k+1 ; ++i ){
		p2k = p2k+p2k;
		if ( p2k >= mod )	p2k -= mod;
	}
	for ( int i = 1 ; i <= k ; ++i ){
		pp = pp+pp;
		if ( pp >= mod )	pp -= mod;
	}
	
	V.reserve(mod);
	
	int val = 0,perioada = 0;
	for ( ; ; ){
		
		if ( !in[val] ){
			in[val] = 1;
			V.push_back(val);
			++perioada;
		}
		else{
			break ;
		}
		
		val = (1LL*p2k*val + p2k)%mod;
	}
	
	for ( int i = 1 ; i <= tests ; ++i ){
		
		scanf("%s",sir+1); int len = strlen(sir+1);
		
		int from = 0;
		for ( int i = 1 ; i <= len ; ++i ){
			from = (from*10+sir[i]-'0')%perioada;
		}
		--from;
		if ( from < 0 )	from += perioada;
		
		
		int sol = (1LL*(V[from]+1) * pp)%mod;
		printf("%d\n",sol);
	}
	
	return 0;
}