#include<bits/stdc++.h>
using namespace std;
int const maxn = 1e5 + 10, mod = 1e9 + 9;
int n, k, dp[maxn], x[maxn];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> k;
	for (int i = 0; i < k; ++i)
        cin >> x[i];
    dp[0] = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j < k; ++j)
            if (i >= x[j]){
                dp[i] += dp[i - x[j]];
                dp[i] %= mod;
            }
    cout << dp[n] << endl;
return 0;
}