# -*- coding:utf-8 -*-
if __name__ == '__main__':
    x, n = map(int, input().split())
    an = map(int, input().split())
    answer = 0
    for a in an:
        answer += x ** a % 1000003
    print(answer % 1000003)