#include<cstdio>
#include<math.h>
#define MAXN 100002
#define int long long
using namespace std;
int n, k, dp[MAXN];
int arr[MAXN], ans;
int MOD = 1000000000 + 9;
signed main()
{
    freopen("steps.in", "r", stdin);
    freopen("steps.out", "w", stdout);
    scanf("%lld", &n);
    scanf("%lld", &k);
    for(int i = 0; i < k; i ++)
    {
        scanf("%lld", &arr[i]);
        //cout<<arr[i]<<endl;
    }
    dp[0] = 1;
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 0; j < k; j ++)
        {
            if(i >= arr[j])
            {
                dp[i] += dp[i - arr[j]];
                //cout<<dp[i]<<endl;
                //cout<<i<<" "<<arr[j]<<endl;
            }
        }

    }
    dp[n] %= MOD;
    printf("%lld\n", dp[n]);
    return 0;
}