#include <cstdio>
#include <cstring>

using namespace std;

const int kmod = 666013;

int fpow(int base, int exp){
  if(exp == 0)
    return 1;
  if(exp == 1){
    return base;
  }

  int aux = fpow(base, exp / 2);
  aux = (long long) aux * aux % kmod;
  if(exp & 1)
    aux = (long long) aux * base % kmod;
  return aux;
}

int main(){
  #ifndef ONLINE_JUDGE
    freopen("isk.in", "r", stdin);
  #endif

  int t, k;
  scanf("%d%d\n", &t, &k);

  while(t --){
    char lel;
    int num = 0;
    while(1){
      scanf("%c", &lel);
      if(lel > '9' || lel < '0')
        break;
      else{
        num = num * 10 + lel - '0';
        num %= kmod;
      }
    }
    int a = fpow(2, k);
    int b = fpow(fpow(2, k + 1), num) - 1;
    int c = fpow(fpow(2, k + 1) - 1, kmod - 2);
    int ans = (long long)a * b % kmod * c % kmod;
    printf("%d\n", ans);
  }

  return 0;
}