#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <fstream>


using namespace std;
const int mod = 666013;
int per[] = {0,
	666013, 333007, 222005, 166504, 666013, 111003, 666013, 166504, 222005, 333007, 666013, 55502, 666013, 333007, 222005, 166504, 666013, 		111003, 666013, 166504, 222005, 333007, 666013, 55502, 666013, 333007, 222005, 166504, 666013, 111003, 666013, 166504, 222005, 333007, 		666013, 55502, 666013, 333007, 222005, 166504, 666013, 111003, 666013, 166504, 222005, 333007, 666013, 55502, 666013, 333007, 222005, 		166504, 666013, 111003, 666013, 166504, 222005, 333007, 666013, 55502, 666013, 333007, 222005, 166504, 666013, 111003, 666013, 166504, 		222005, 333007, 666013, 55502, 666013, 333007, 222005, 166504, 666013, 111003, 666013, 166504, 222005, 333007, 666013, 55502, 666013, 		333007, 222005, 166504, 666013, 111003, 666013, 166504, 222005, 333007, 666013, 55502, 666013, 333007, 222005, 166504
};

int main() {
    /*
    ifstream cin("test.in");
    ofstream cout("test.out");
    */
    cin.sync_with_stdio(false);
    int T; cin >> T;
    int K; cin >> K;
    vector <long long> pw(mod+2);
    pw[0] = 1;

    for (int i = 1; i <= mod; ++i) {
        pw[i] = (pw[i - 1] * 2) % mod;
    }

    vector <long long> answer(mod+2, 0);
    answer[0] = 1;
    answer[1] = pw[K];
    for (int i = 2; i <= mod; ++i) {
        answer[i] = (answer[i - 1] * pw[K + 1] + pw[K]) % mod;
    }
    
    for (int test = 1; test <= T; ++test) {
        string s; 
        cin >> s; 
        long long t = 0;

        reverse(s.begin(), s.end());
        
        for (int i = s.size() - 1; i >= 0; --i) {
            t = (t * 10 + s[i] - '0') % per[K] ;
        }
        cout << answer[t] << "\n";   
    }
    return 0;
}