#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int n, k, a[101];
long long dp[1000001];
void in()
{ scanf("%d %d", &n, &k);
  for (int i = 0; i < k; i++)
    scanf("%d", &a[i]);
}

long long solve(long long n1)
{ if (n1 < 0)
    return 0;
  
  if (n1 == 0)
    return 1;
  
  if (dp[n1] != -1)
    return dp[n1];
  
  long long ans = 0;
  for (int i = 0; i < k; i++)
  { ans += solve(n1 - a[i]);
    ans %= 1000003;
  }
  
  return dp[n1] = ans;
}

int main()
{ 
  in();
  memset(dp, -1, sizeof(dp));
  printf("%lld\n", solve(n));
  
  return 0;
}