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

int t, k;
int n;
char s[1000005];
const int mod = 666013;

int imp()
{
      int i, t = 0;
      for (i = 1; i <= n; i++)
              t = (t * 10 + s[i] - '0') % mod;
      return t;
}

long long pow (long long x, long long p)
{
	if (p == 0)
		return 1;
	if (p == 1)
		return x % mod;
	long long y = pow (x, p / 2);
	y = y * y % mod;
	if (p & 1)
		y = y * x % mod;
	return y;
}

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

	scanf ("%d %d\n", &t, &k);
	
	k ++;
	long long sol;
	while (t --)
	{
		gets (s + 1);
		n = strlen (s + 1);
		
		int rest = imp();
		sol = (pow (2, (long long)rest * k) -1 + mod) % mod;
		int inv = (pow (2, k) -1 + mod) % mod;
		inv = pow (inv, mod - 2);
		sol = sol * pow (2, k - 1) % mod;
		sol = sol * inv % mod;
		int x = sol % mod;
		printf ("%d\n", x);
	}
	return 0;
}