/* 
 *     Author:  srtry
 *     Created: 2025-05-10T06:05:13+09:00
 *     Coding:  utf-8-unix
 */

use proconio::input;
use std::io::{stdout,Write,BufWriter};
use std::collections::HashMap;

const big:usize = 1000003;

fn pow_mod(&x:&usize, &n:&usize, mem:&mut HashMap<usize,usize>) -> usize {
    if mem.contains_key(&n) {
        return mem[&n];
    }

    if n==1 {
        let tmp = x%big;
        mem.insert(1, tmp);
        return x%big;
    } else if n==0 {
        mem.insert(0,1);
        return 1;
    }

    let tmp:usize = pow_mod(&x, &(n/2), mem);
    if n%2 == 0 {
        mem.insert(n, (tmp*tmp)%big);
        return (tmp*tmp)%big;
    } else {
        mem.insert(n, (tmp*tmp*x)%big);
        return (tmp*tmp*x)%big;
    }
}

fn main() {
    input!{
        x:usize, n:usize,
        a:[usize;n]
    }

    let out = stdout();
    let mut out = BufWriter::new(out.lock());
    let mut mem:HashMap<usize,usize> = HashMap::new();

    let mut ans:usize = 0;
    for elem in a.iter() {
        ans += pow_mod(&x, elem, &mut mem);
        ans = ans%big;
    }

    write!(out, "{}", ans).unwrap();
}