row = raw_input().split(' ')
n = int(row[0])
m = int(row[1])
lista = []
listaBin = []
# construct 
while(n > 0):
    nr = int(raw_input())
    lista.append(nr)
    n = n - 1

k = pow(10, m)

# construct answers
for nr in lista:
    t = k
    while(nr > 1):
        t = k + t*k*10
        nr = nr - 1
    listaBin.append(t)
    

for item in listaBin:
    print int(str(item), 2)%666013