//Code by Patcas Csaba

#include <vector>
#include <string> 
#include <set> 
#include <map> 
#include <queue> 
#include <bitset> 
#include <stack>
#include <list>

#include <numeric> 
#include <algorithm> 

#include <cstdio>
#include <fstream>
#include <iostream> 
#include <sstream> 
#include <iomanip>

#include <cctype>
#include <cmath> 
#include <ctime>
#include <cassert>

using namespace std;

#define LL long long
#define PII pair <int, int>
#define VB vector <bool>
#define VI vector <int>
#define VD vector <double>
#define VS vector <string>
#define VPII vector <pair <int, int> >
#define VVI vector < VI >
#define VVB vector < VB >

#define FORN(i, n) for(int i = 0; i < (n); ++i)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define REPEAT do{ 
#define UNTIL(x) }while(!(x)); 

#define SZ size()
#define BG begin() 
#define EN end() 
#define CL clear()
#define X first
#define Y second
#define RS resize
#define PB push_back
#define MP make_pair
#define ALL(x) x.begin(), x.end()

#define in_file "a.in"
#define out_file "a.out"

#define BASE 666013

int k, test;
LL pk;
VI allPk(BASE + 1), atIndex(BASE, -1);
string n;

long long S2I(string a) 
{
   stringstream ss(a);
   long long answer;
   ss >> answer;
   return answer;
}

string I2S(long long a) {
   stringstream s;
   s << a;
   return s.str();
}

string substract(string s1, int x)
{
	string s2 = I2S(x);
	vector <char> aans;
	while (s2.SZ < s1.SZ) s2 = '0' + s2;
	int r = 0;
	aans.RS(s1.SZ);
	FORD(i, s1.SZ - 1, 0)
	{
		int d1 = s1[i] - '0';
		int d2 = s2[i] - '0';
		r = (d1 - r < d2 ? 1 : 0);
		int newDig;
		if (r) newDig = 10 + d1 - d2;
		else newDig = d1 - d2;
		aans[i] = newDig + '0';
	}
	string ans = "";
	FORN(i, aans.SZ) ans = ans + aans[i];
	return ans;
}

int main()
{
	//Read data
	//freopen(in_file, "r", stdin);
	//freopen(out_file, "w", stdout);
	
	cin >> test >> k;

	pk = 1;
	FOR(i, 1, k) pk = (pk * 2) % BASE;
	allPk[1] = pk;
	atIndex[pk] = 1;
	int start = -1, period = -1;
	FOR(i, 2, BASE)
	{
		allPk[i] = ((LL)allPk[i - 1] * pk * 2 + pk) % BASE;
		if (atIndex[allPk[i]] != -1)
		{
			start = atIndex[allPk[i]];
			period = i - atIndex[allPk[i]];
		}
		atIndex[allPk[i]] = i;
	}


	FORN(t, test)
	{
		cin >> n;
		if (n.SZ <= 7)
		{
			int nInt = S2I(n);
			if (nInt <= start) cout << allPk[nInt] << endl;
			continue;
		}

		n = substract(n, start);
		int nModPeriod = 0;
		FORN(i, n.SZ) 
		{
			nModPeriod = (nModPeriod * 10 + (n[i] - '0')) % period;
		}
		cout << allPk[start + nModPeriod] << endl;
	}
	//Solve

	//Write data


	return 0;
}