q=1e6+3,s,c;m(x){return x?(x%2?c:1)*1L*(x=m(x/2))*x%q:1;}main(t){for(scanf("%d%*d",&c);~scanf("%d",&t);s+=m(t));t=!printf("%d",s%q);}