x,*a=$<.read.split
p eval("0*"+a*"+#{x}**")%1000003