#include <stdio.h>
#include <stdlib.h>
#include <string.h>

 #define NO_FILES

int N, k;

const int MOD = 666013;
const int MAXN = 10000000;

int r[MAXN];
int pow2[128];
int cycle_length;

char buffer[1 << 20];

typedef long long ll;

int main() {
	#ifndef NO_FILES
	freopen(stdin, "numeremari.in", "r");
	freopen(stdout, "numeremari.out", "w");
	#endif

	scanf("%d %d", &N, &k);
	// precompute 2^k % MOD
	pow2[0] = 1;
	for (int i = 1; i < 128; ++i) {
		pow2[i] = (pow2[i-1] * 2) % MOD;
	}

	int group = pow2[k];
	for (int i = 1; i < MOD; ++i) {
		r[i] = ((ll)((ll)r[i-1] * pow2[k + 1]) + group) % MOD;
		if (r[i] == 0) {
			cycle_length = i;
			break;
		}
	}

	for (int i = 1; i <= N; ++i) {
		scanf("%s\n", buffer);
		int length = strlen(buffer);
		int index = 0;
		for (int j = 0; j < length; ++j) {
			index = (index * 10 + buffer[j] - '0') % cycle_length;
		}
		printf("%d\n", r[index]);
	}

	return 0;
}