#!/usr/bin/env python3
import sys
input = sys.stdin.readline

x, n = map(int, input().split())
mod = 10**6 + 3
a = [int(item) for item in input().split()]
ans = 0
for item in a:
    ans += pow(x, item, mod)
    ans %= mod

print(ans)