a=[123456789,362436069,521288629,88675123]
A=->{t=a[0]^a[0]<<11
a.shift
a+=[w=a[-1]^(a[-1]>>19)^t^t>>8]
w}
d=100003
n,_,*q=$<.read.split.map &:to_i
r=n.times.map{A[]%d}
p n.times{|i|r[i]*q[i]%d}.max