mod = 1000003


def main():
    x, n = map(int, input().split())
    ans = 0
    for a in map(int, input().split()):
        ans += pow(x, a, mod)
        ans %= mod

    print(ans % mod)
    
if __name__ == '__main__':
    main()