#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int MOD = 666013;

int T, K;
char A[1000010];

int power(int x, int y)
{
	if (y == 0) return 1;
	if (y & 1) return 1LL * x * power(x, y - 1) % MOD;
	return power(1LL * x * x % MOD, y / 2);
}

int main()
{
	cin.sync_with_stdio(false);
	
	cin >> T >> K;
	++K;
	
	while (T--)
	{
		cin >> A;
		
		int rest = 0;
		for (int i = 0; A[i] != 0; ++i)
			rest = (1LL * rest * 10 + (A[i] - '0')) % (MOD - 1);
			
		++rest;
		if (rest >= MOD) rest -= MOD;
		
		int now = power(2, K);
		
		int result = power(now, rest) - 1;
		if (result < 0) result += MOD;

		result = 1LL * result * power((MOD + now - 1) % MOD, MOD - 2) % MOD;
		
		--result;
		if (result < 0) result += MOD;
		
		result = 1LL * result * power(2, MOD - 2) % MOD;
		
		cout << result << '\n';
	}
}