# -*- coding:utf-8 -*-
# http://yukicoder.me/problems/42
M = 1000003

def my_pow(x, n):
    ret = 1
    while 0 < n:
        if n % 2 == 0:
            x *= x % M
            n >>= 1
        else:
            ret *= x % M
            n -= 1
    return ret
if __name__ == '__main__':
    x, n = map(int, input().split())
    an = map(int, input().split())
    answer = 0
    x %= 1000003
    for a in an:
        p = my_pow(x, a)
        answer += p % M
    print(answer % M)