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

#define MOD 666013

int T, K, i, RBASE, RBASE2;

void ComputeRBASE() {
	RBASE = 1;
	for (int i = 1; i <= K; i++)
		RBASE = (RBASE * 2) % MOD;
	RBASE2 = (RBASE * 2) % MOD;
}

int first[MOD], sum[MOD + 1], CLEN;

void FindRepetitions() {
	int i, C = 1;

	for (i = 0; i < MOD; i++)
		first[i] = -1;

	sum[0] = 0;
	for (i = 0; 1; i++) {
		if (first[C] >= 0) {
			CLEN = i;
			break;
		}

		first[C] = i;
		sum[i + 1] = (sum[i] + C) % MOD;
		//if (sum[i + 1] == 0)
		//	fprintf(stderr, "! %d\n", i + 1);

		C = ((long long) C * (long long) RBASE2) % MOD;
	}

	//fprintf(stderr, "K=%d CLEN=%d sum=%d\n", K, CLEN, sum[CLEN]);
}

#define LMAX 1111111
char A[LMAX];
int L, ar, ans;

void GetRemainder() {
	ar = 0;
	for (int i = 0; i < L; i++)
		ar = (ar * 10 + (A[i] - '0')) % CLEN;
}

int main() {
	scanf("%d %d", &T, &K);

	ComputeRBASE();
	FindRepetitions();

	while (T--) {
		scanf("%s", A);
		L = strlen(A);
		
		GetRemainder();
		//fprintf(stderr, "ar=%d : %d\n", ar, sum[ar]);

		ans = ((long long) sum[ar] * (long long) RBASE) % MOD;
		printf("%d\n", ans);
	}

	return 0;
}