#include <fstream>
#include <iostream>
#include <vector>
#include <bitset>
#include <string.h>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <time.h>
#include <stdlib.h>
#include <set>
#include <map>
#include <string>
#include <queue>
#include <deque>

using namespace std;

const char infile[] = "input.in";
const char outfile[] = "output.out";

ifstream fin(infile);
ofstream fout(outfile);

const int MAXN = 1000005;
const int oo = 0x3f3f3f3f;
const int MOD =  666013;

typedef vector<int> Graph[MAXN];
typedef vector<int> :: iterator It;

const inline int min(const int &a, const int &b) { if( a > b ) return b;   return a; }
const inline int max(const int &a, const int &b) { if( a < b ) return b;   return a; }
const inline void Get_min(int &a, const int b)    { if( a > b ) a = b; }
const inline void Get_max(int &a, const int b)    { if( a < b ) a = b; }

int N, K;
string s;
vector <int> v;
bitset <MOD + 5> Used;

inline int lgPow(int a, int p) {
    int Ans = 1;
    a %= MOD;
    for( ; p ; p >>= 1) {
        if(p & 1)
            Ans = (1LL * Ans * a) % MOD;
        a = (1LL * a * a) % MOD;
    }
    return Ans;
}

inline int invMod(int a) {
    return lgPow(a, MOD - 2);
}

inline int modulo(string x, int period) {
    int ans = 0;
    for(int i = 0 ; i < x.size() ; ++ i)
        ans = (ans * 10 + (x[i] - '0')) % MOD;
    return ans;
}

int main() {
    int period = 0;
    #ifndef ONLINE_JUDGE
    freopen(infile, "r", stdin);
    freopen(outfile, "w", stdout);
    #endif // ONLINE_JUDGE
    cin >> N >> K;
    int a1 = lgPow(2, K);
    int inv = invMod((2LL * a1 + MOD - 1) % MOD);
    a1 = a1 * inv;
    int multiply = lgPow(2, K + 1);
    int actNb = multiply;
    Used[actNb] = 1;
    ++ period;
    v.push_back(actNb);
    while(true) {
        actNb = (1LL * actNb * multiply) % MOD;
        if(Used[actNb])
            break;
        Used[actNb] = true;
        ++ period;
        v.push_back(actNb);
    }
    for(int i = 1 ; i <= N ; ++ i) {
        cin >> s;
        int ind = modulo(s, period);
        cout << (1LL * a1 * (v[ind - 1] - 1 + MOD)) % MOD;
    }
    fin.close();
    fout.close();
    return 0;
}