x, n = map(int,input().split())
power_list = list(map(int, input().split()))
power_list.append(0)
power_list.sort()
power = x
ans = 0
for i in range(1, n+1):
    if power_list[i] == 0:
        ans += 1
    else:
        step = power_list[i] - power_list[i - 1]
        if step == 0:
            ans += power
        elif power_list[i - 1] == 0:
            power = power**step
            ans += power
        else:
            power = power * (x**step)
            ans += power
print(ans % 1000003)