Mod = 666013


def inm(a, b):
	c = [0, 0, 0, 0]
 	for i in range (0, 2):
		for j in range (0, 2):
			for d in range(0, 2):
				c[i * 2 + j] += a[i * 2 + d] * b[d * 2 + j]
				c[i * 2 + j] %= Mod
	return c

def solve(a, p):
	rez = [1, 0, 1, 0]
	while p > 0:
		if p % 2 == 1:
			rez = inm(rez, a)
		a = inm(a, a)
		p /= 2
	return rez

aux = raw_input().split()
t = int(aux[0])
k = int(aux[1])

query = []

for i in range(0, t):
	x = int(raw_input())
	query.append(long(x))

a = int(1)

for i in range(0, k):
	a = a * 2
	a = a % Mod
b = a
a = a * 2
a = a % Mod

for itr in query:
	aux = [a, b, 0, 1]
	rez = solve(aux, itr)
	print rez[1]