fn read_line()->String{ let mut x = String::new(); let r = std::io::stdin().read_line(& mut x); x } fn bin_pow(x:u64, mut n:u64)->u64{ let mut y:u64 = 1; let mut p:u64 = x; while n > 0{ if n % 2 == 0 { p = (p % 1000003) * (p % 1000003); n /= 2; } else{ y = (y%1000003) * (p % 1000003); n -= 1; } } y } fn main() { let a = read_line(); let a_array:Vec<&str> = a.split(' ').collect(); let base = a_array[0].parse::().unwrap(); let b = read_line(); let trimed_b = b.trim(); let numbers_s: Vec<&str> = trimed_b.split(' ').collect(); let mut sum:u64 = 0; for num_s in numbers_s{ let num= num_s.parse::().unwrap(); //println!("{}", base); sum += bin_pow(base, num)%1000003; } println!("{}", sum); }