print((function (g, fh, m)
	local f,r = g(fh:read("*n"),m),0
	for _=1,fh:read("*n") do r=r+f(fh:read("*n"))%m end
	return r%m
end)(function (x, m)
	local ba,rs = bit.band,bit.rshift
	return function (n)
		local r=1
		while n~=0 do r,x,n=ba(n,1)~=0 and r*(x%m) or r,x*(x%m),rs(n,1) end
		return r
	end
end, io.stdin, 1000003))