use std::io::Read;
const MOD: u64 = 1_000_003;

fn main() {
    let mut s = String::new();
    std::io::stdin().read_to_string(&mut s).ok();
    let mut itr = s.trim().split_whitespace();
    let x: u64 = itr.next().unwrap().parse().unwrap();
    let n: u64 = itr.next().unwrap().parse().unwrap();

    let mut ans: u64 = 0;
    for _ in 0..n {
        let mut e: u64 = itr.next().unwrap().parse().unwrap();
        let mut tx = x;
        let mut res: u64 = 1;
        while e > 0 {
            if e & 1 != 0 {
                res = res * tx % MOD;
            }
            tx = tx * tx % MOD;
            e >>= 1;
        }
        ans = (ans + res) % MOD;
    }
    println!("{}", ans);
}