#include <iostream>
#include <vector>
#include <stdlib.h>

using namespace std;

typedef long long ll;

const int MOD = 1e9 + 7; // change if needed

struct Modint {
  ll val;

  constexpr Modint (ll _val = 0)
    : val(_val % MOD) {}

  constexpr Modint operator+ (Modint other) const {
    return Modint(val + other.val);
  }

  constexpr void operator+= (Modint other) {
    val += other.val;
    val %= MOD;
  }

  constexpr Modint operator- () const {
    return Modint(MOD - val);
  }

  constexpr Modint operator- (Modint other) const {
    return Modint(val + MOD - other.val);
  }

  constexpr void operator-= (Modint other) {
    val += MOD - other.val;
    val %= MOD;
  }

  constexpr Modint operator* (Modint other) const {
    return Modint(val * other.val);
  }

  constexpr void operator*= (Modint other) {
    val *= other.val;
    val %= MOD;
  }

  constexpr bool operator== (Modint other) const {
    return val == other.val;
  }

  constexpr bool operator!= (Modint other) const {
    return val != other.val;
  }
};

constexpr Modint exp (Modint a, int k) {
  if (k == 0) {
    return Modint(1);
  } else if (k % 2 == 0) {
    Modint half = exp(a, k / 2);
    return half * half;
  } else {
    return a * exp(a, k - 1);
  }
}

constexpr Modint inv (Modint a) {
  return exp(a, MOD - 2);
}

ostream& operator<< (ostream& out, Modint p) {
  out << p.val;
  return out;
}

// F_Mod [X] / (x^3 - 2x^2 + 4x - 1)
struct FieldExt {
  Modint a, b, c;

  constexpr FieldExt (ll _x) :
    a(Modint(_x)), b(Modint(0)), c(Modint(0)) {}
  
  constexpr FieldExt (Modint _a = Modint(0),
            Modint _b = Modint(0),
            Modint _c = Modint(0)) :
    a(_a), b(_b), c(_c) {}

  constexpr FieldExt operator+ (FieldExt other) const {
    return FieldExt(a + other.a, b + other.b, c + other.c);
  }

  constexpr FieldExt operator- () const {
    return FieldExt(-a, -b, -c);
  }

  constexpr FieldExt operator- (FieldExt other) const {
    return FieldExt(a - other.a, b - other.b, c - other.c);
  }
  
  constexpr FieldExt operator* (FieldExt other) const {
    return FieldExt(a * other.a
                    + b * other.c + c * other.b
                    + Modint(2) * c * other.c,
                    a * other.b + b * other.a
                    - Modint(4) * b * other.c - Modint(4) * c * other.b
                    - Modint(7) * c * other.c,
                    a * other.c + b * other.b + c * other.a
                    + Modint(2) * b * other.c + Modint(2) * c * other.b);
  }

  constexpr bool operator== (FieldExt other) const {
    return a == other.a && b == other.b && c == other.c;
  }
};

constexpr FieldExt exp (FieldExt a, int k) {
  if (k == 0) {
    return FieldExt(1);
  } else if (k % 2 == 0) {
    FieldExt half = exp(a, k / 2);
    return half * half;
  } else {
    return a * exp(a, k - 1);
  }
}

constexpr FieldExt inv (FieldExt a) {
  FieldExt b = exp(a, MOD - 2);
  FieldExt c = exp(exp(a, MOD), MOD - 1);
  FieldExt d = exp(exp(exp(a, MOD), MOD), MOD - 1);
  return b * c * d;
}

ostream& operator<< (ostream &out, FieldExt p) {
  out << "(" << p.a << " " << p.b << " " << p.c << ")";
  return out;
}

FieldExt randf () {
  return FieldExt(Modint(rand()), Modint(rand()), Modint(rand()));
}

const FieldExt ROOT1 (Modint(0), Modint(1), Modint(0));
const FieldExt ROOT2 = exp(ROOT1, MOD);
const FieldExt ROOT3 = exp(ROOT2, MOD);
const FieldExt ROOT [3] = {ROOT1, ROOT2, ROOT3};

FieldExt P (FieldExt x) {
  return x * x * x - FieldExt(2) * x * x + FieldExt(4) * x - FieldExt(1);
}

FieldExt pins [3][3];
FieldExt cbs [3];

// x^k modulo (x^3 - 2x^2 + 4x - 1)
vector<FieldExt> xk (int K) {
  vector<FieldExt> ys (3);
  for (int i = 0; i < 3; i++) {
    ys[i] = exp(ROOT[i], K) * cbs[i];
  }
  vector<FieldExt> res (3, FieldExt(0));
  vector<FieldExt> temp (3);

  for (int k = 0; k < 3; k++) {
    for (int i = k + 1; i < 3; i++) {
      ys[i] = (ys[i] - ys[k]) * pins[i][k];
    }
  }

  FieldExt last (0);
  temp[0] = FieldExt(1);
  for (int k = 0; k < 3; k++) {
    for (int i = 0; i < 3; i++) {
      res[i] = res[i] + ys[k] * temp[i];
      swap(last, temp[i]);
      temp[i] = temp[i] - last * ROOT[k];
    }
  }
  return res;
}

// transforms (A, B, C) to a polynomial
const FieldExt MATX [3][3] =
  {
    {   ROOT[1] * ROOT[2],    ROOT[0] * ROOT[2],    ROOT[0] * ROOT[1]},
    {-(ROOT[1] + ROOT[2]), -(ROOT[0] + ROOT[2]), -(ROOT[0] + ROOT[1])},
    {         FieldExt(1),          FieldExt(1),          FieldExt(1)}
  };

vector<FieldExt> ipfd (vector<FieldExt> v) {
  vector<FieldExt> ans (3, FieldExt(0));
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      ans[i] = ans[i] + MATX[i][j] * v[j];
    }
  }
  return ans;
}

// transforms a polynomial to the pfd, inverse of MATX
FieldExt IMATX [3][3];
vector<int> os [3] = {{1, 2}, {0, 2}, {0, 1}};

// partial fraction decomposition of v / (x^3 - 2x^2 + 4x - 1)
vector<FieldExt> pfd (vector<FieldExt> v) {
  vector<FieldExt> ans (3, FieldExt(0));
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      ans[i] = ans[i] + IMATX[i][j] * v[j];
    }
  }
  return ans;
}

FieldExt iroot [3];
FieldExt eval (const vector<FieldExt> &coefs, int K) {
  FieldExt ans (0);
  for (int i = 0; i < 3; i++) {
    ans = ans + coefs[i] * exp(iroot[i], K + 1);
  }
  return -ans;
}

const int MAX_N = 1e5 + 5;
int arr [MAX_N];

int main () {
  for (int i = 0; i < 3; i++) {
    cbs[i] = (ROOT[i] - 1) * (ROOT[i] - 1) * (ROOT[i] - 1);
    iroot[i] = inv(ROOT[i]);
    for (int j = 0; j < 3; j++) {
      if (i != j) {
        pins[i][j] = inv(ROOT[i] - ROOT[j]);
      }
    }
  }

  // calculate IMATX
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      vector<int> oi = os[i];
      vector<int> oj = os[j];
      IMATX[j][i] = MATX[oi[0]][oj[0]] * MATX[oi[1]][oj[1]]
        - MATX[oi[0]][oj[1]] * MATX[oi[1]][oj[0]];

      if ((i + j) % 2 == 1) {
        IMATX[j][i] = -IMATX[j][i];
      }
    }
  }
  FieldExt det = MATX[0][0] * IMATX[0][0] + MATX[0][1] * IMATX[1][0] + MATX[0][2] * IMATX[2][0];
  FieldExt idet = inv(det);
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      IMATX[i][j] = IMATX[i][j] * idet;
    }
  }

  vector<FieldExt> coefs = pfd(xk(0));

  ios::sync_with_stdio(false);
  int n, m;
  cin >> n >> m;

  for (int i = 0; i < m; i++) {
    cin >> arr[i];
  }

  for (int i = 0; i < m; i++) {
    int K = arr[i];
    FieldExt a = eval(coefs, K);

    vector<FieldExt> ncoefs = pfd(xk(K));
    for (int j = 0; j < 3; j++) {
      coefs[j] = coefs[j] - a * ncoefs[j];
    }
  }

  cout << eval(coefs, n).a << endl;
}


Measured memory_bytes: 4172