#!/usr/bin/env python3
#fileencoding: utf-8

x, _ = [int(i) for i in input().strip().split(" ")]
mod = 1000003
ans = 0
for i in input().strip().split(" "):
    a = int(i)
    tmp = 1
    for j in range(a):
        tmp *= x
        tmp %= mod
    ans += tmp
    ans %= mod
print(ans)