#include <iostream>
#include <vector>
#include <cmath>
#include <ctime>
#include <cassert>
#include <cstdio>
#include <queue>
#include <set>
#include <map>
#include <fstream>
#include <cstdlib>
#include <string>
#include <cstring>
#include <algorithm>
#include <numeric>

#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;

template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

vector<pair<int, vector<pii> > > ts;
map<pair<int, vector<pii> >, int> en;
map<pii, int> trans, wt;

int dfs(int sp, vector<pii> mps) {
    if (sp > 2) return -1;
    for (pii p: mps) {
        if (p.fi > 2 || p.se > 2) return -1;
        if (p.fi > p.se) swap(p.fi, p.se);
    }
    sort(all(mps));
    auto t = mp(sp, mps);
    if (en.count(t)) return en[t];
    en[t] = ts.size();
    ts.pb(t);
    int n = en[t];
//    cerr << n << ' ' << sp << ' ' << mp1 << ' ' << mp2 << '\n';
    for (pii &w: mps) {
        ++w.fi; ++w.se;
    }
    ++trans[mp(n, dfs(0, mps))];
    ++wt[mp(n, dfs(sp + 1, mps))];
    mps.pb(mp(0, 0));
    ++trans[mp(n, dfs(sp + 1, mps))];
    mps.pop_back();
    forn(i, mps.size()) {
        forn(j, 2) {
            vector<pii> nmps = mps;
            nmps[i].fi = 0;
            ++trans[mp(n, dfs(sp + 1, nmps))];
            nmps = mps;
            int t = mps[i].fi;
            nmps.erase(nmps.begin() + i);
            ++trans[mp(n, dfs(t, nmps))];
            if (mps[i].fi == mps[i].se) break;
            swap(mps[i].fi, mps[i].se);
        }
    }
    return n;
}

const i64 P = 100000000 + 2015;

void add(i64 &x, i64 y) {
    x += y; x %= P;
}

vvi64 mul(const vvi64 &a, const vvi64 &b) {
    int n = a.size();
    vvi64 c(n, vi64(n));
    forn(i, n) forn(j, n) forn(k, n) add(c[i][k], a[i][j] * b[j][k]);
    return c;
}

vvi64 deg(vvi64 a, i64 d) {
    int n = a.size();
    vvi64 c(n, vi64(n));
    forn(i, n) c[i][i] = 1;
    while (d) {
        if (d & 1) c = mul(c, a);
        a = mul(a, a);
        d /= 2;
    }
    return c;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.precision(10);
    cout << fixed;
#ifdef LOCAL_DEFINE
    freopen("input.txt", "rt", stdin);
#endif

    dfs(0, vector<pii>());
    cerr << ts.size() << '\n';

    int K = ts.size();
    vvi64 mt(K, vi64(K)), mw(K, vi64(K));
    for (auto w: trans) {
        int x = w.fi.fi, y = w.fi.se;
        if (y == -1) continue;
        mt[x][y] = w.se;
    }

    for (auto w: wt) {
        int x = w.fi.fi, y = w.fi.se;
        if (y == -1) continue;
        mw[x][y] = w.se;
    }
    i64 N, M;
    cin >> N >> M;
    vi64 a(M + 1);
    a[0] = 1;
    for1(i, M) cin >> a[i];
    vvi64 m(K, vi64(K));
    forn(i, K) m[i][i] = 1;
    forn(i, M) {
        m = mul(m, deg(mt, a[i + 1] - a[i] - 1));
        m = mul(m, mw);
    }
    m = mul(m, deg(mt, N - a.back()));
    cout << m[0][0] << '\n';

#ifdef LOCAL_DEFINE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}