import java.io.*; import java.util.StringTokenizer; import java.math.BigInteger; class Main{ static final PrintWriter out=new PrintWriter(System.out); static final int mod=1000003; public static void main(String[] args) throws IOException{ BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); String line=""; while((line=br.readLine())!=null&&!line.isEmpty()){ StringTokenizer st1=new StringTokenizer(line); int n=Integer.parseInt(st1.nextToken()); line=br.readLine(); StringTokenizer st2=new StringTokenizer(line); int ans=0; while(st2.hasMoreTokens()){ int a=Integer.parseInt(st2.nextToken()); ans+=pow_mod_1000003(n,a); ans%=mod; } out.println(ans); out.flush(); } } private static int pow_mod_1000003(int n,int a){ int p=1; if(a==0) return 1; if(n==0) return 0; if(n==1) return 1; for(int i=0;i<=a;i++){ if(p>=mod){ return (pow_mod_1000003(p%mod,(int)a/i)*(int)Math.pow(n,a%i))%mod; } if(i==a) break; p*=n; } return p; } }