Problem: Brian the Rabbit adores chess. Not long ago he argued with Stewie the Rabbit that a knight is better than a king. To prove his point he tries to show that the knight is very fast but Stewie doesn't accept statements without evidence. He constructed an infinite chessboard for Brian, where he deleted several squares to add some more interest to the game. Brian only needs to count how many different board squares a knight standing on a square with coordinates of (0, 0) can reach in no more than k moves. Naturally, it is forbidden to move to the deleted squares.

Brian doesn't very much like exact sciences himself and is not acquainted with programming, that's why he will hardly be able to get ahead of Stewie who has already started solving the problem. Help Brian to solve the problem faster than Stewie.

Input

The first line contains two integers k and n (0 ≤ k ≤ 1018, 0 ≤ n ≤ 440) which are correspondingly the maximal number of moves a knight can make and the number of deleted cells. Then follow n lines, each giving the coordinates of a deleted square in the form (xi, yi) (|xi| ≤ 10, |yi| ≤ 10). All the numbers are integer, the deleted squares are different and it is guaranteed that the square (0, 0) is not deleted.

Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cin (also you may use %I64d).

Output

You must print the answer on a single line. As it can be rather long, you should print it modulo 1000000007.

Examples

Input

1 0


Output

9


Input

2 7
-1 2
1 2
2 1
2 -1
1 -2
-1 -2
-2 -1


Output

9

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
template <typename T>
T inverse(T a, T m) {
  T u = 0, v = 1;
  while (a != 0) {
    T t = m / a;
    m -= t * a;
    swap(a, m);
    u -= t * v;
    swap(u, v);
  }
  assert(m == 1);
  return u;
}
template <typename T>
class Modular {
 public:
  using Type = typename decay<decltype(T::value)>::type;
  constexpr Modular() : value() {}
  template <typename U>
  Modular(const U& x) {
    value = normalize(x);
  }
  template <typename U>
  static Type normalize(const U& x) {
    Type v;
    if (-mod() <= x && x < mod())
      v = static_cast<Type>(x);
    else
      v = static_cast<Type>(x % mod());
    if (v < 0) v += mod();
    return v;
  }
  const Type& operator()() const { return value; }
  template <typename U>
  explicit operator U() const {
    return static_cast<U>(value);
  }
  constexpr static Type mod() { return T::value; }
  Modular& operator+=(const Modular& other) {
    if ((value += other.value) >= mod()) value -= mod();
    return *this;
  }
  Modular& operator-=(const Modular& other) {
    if ((value -= other.value) < 0) value += mod();
    return *this;
  }
  template <typename U>
  Modular& operator+=(const U& other) {
    return *this += Modular(other);
  }
  template <typename U>
  Modular& operator-=(const U& other) {
    return *this -= Modular(other);
  }
  Modular& operator++() { return *this += 1; }
  Modular& operator--() { return *this -= 1; }
  Modular operator++(int) {
    Modular result(*this);
    *this += 1;
    return result;
  }
  Modular operator--(int) {
    Modular result(*this);
    *this -= 1;
    return result;
  }
  Modular operator-() const { return Modular(-value); }
  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, int>::value,
                     Modular>::type&
  operator*=(const Modular& rhs) {
    value = normalize(static_cast<int64_t>(value) *
                      static_cast<int64_t>(rhs.value));
    return *this;
  }
  template <typename U = T>
  typename enable_if<is_same<typename Modular<U>::Type, int64_t>::value,
                     Modular>::type&
  operator*=(const Modular& rhs) {
    int64_t q = static_cast<int64_t>(static_cast<long double>(value) *
                                     rhs.value / mod());
    value = normalize(value * rhs.value - q * mod());
    return *this;
  }
  template <typename U = T>
  typename enable_if<!is_integral<typename Modular<U>::Type>::value,
                     Modular>::type&
  operator*=(const Modular& rhs) {
    value = normalize(value * rhs.value);
    return *this;
  }
  Modular& operator/=(const Modular& other) {
    return *this *= Modular(inverse(other.value, mod()));
  }
  template <typename U>
  friend const Modular<U>& abs(const Modular<U>& v) {
    return v;
  }
  template <typename U>
  friend bool operator==(const Modular<U>& lhs, const Modular<U>& rhs);
  template <typename U>
  friend bool operator<(const Modular<U>& lhs, const Modular<U>& rhs);
  template <typename U>
  friend std::istream& operator>>(std::istream& stream, Modular<U>& number);

 private:
  Type value;
};
template <typename T>
bool operator==(const Modular<T>& lhs, const Modular<T>& rhs) {
  return lhs.value == rhs.value;
}
template <typename T, typename U>
bool operator==(const Modular<T>& lhs, U rhs) {
  return lhs == Modular<T>(rhs);
}
template <typename T, typename U>
bool operator==(U lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) == rhs;
}
template <typename T>
bool operator!=(const Modular<T>& lhs, const Modular<T>& rhs) {
  return !(lhs == rhs);
}
template <typename T, typename U>
bool operator!=(const Modular<T>& lhs, U rhs) {
  return !(lhs == rhs);
}
template <typename T, typename U>
bool operator!=(U lhs, const Modular<T>& rhs) {
  return !(lhs == rhs);
}
template <typename T>
bool operator<(const Modular<T>& lhs, const Modular<T>& rhs) {
  return lhs.value < rhs.value;
}
template <typename T>
Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) += rhs;
}
template <typename T, typename U>
Modular<T> operator+(const Modular<T>& lhs, U rhs) {
  return Modular<T>(lhs) += rhs;
}
template <typename T, typename U>
Modular<T> operator+(U lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) += rhs;
}
template <typename T>
Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) -= rhs;
}
template <typename T, typename U>
Modular<T> operator-(const Modular<T>& lhs, U rhs) {
  return Modular<T>(lhs) -= rhs;
}
template <typename T, typename U>
Modular<T> operator-(U lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) -= rhs;
}
template <typename T>
Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) *= rhs;
}
template <typename T, typename U>
Modular<T> operator*(const Modular<T>& lhs, U rhs) {
  return Modular<T>(lhs) *= rhs;
}
template <typename T, typename U>
Modular<T> operator*(U lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) *= rhs;
}
template <typename T>
Modular<T> operator/(const Modular<T>& lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) /= rhs;
}
template <typename T, typename U>
Modular<T> operator/(const Modular<T>& lhs, U rhs) {
  return Modular<T>(lhs) /= rhs;
}
template <typename T, typename U>
Modular<T> operator/(U lhs, const Modular<T>& rhs) {
  return Modular<T>(lhs) /= rhs;
}
template <typename T, typename U>
Modular<T> power(const Modular<T>& a, const U& b) {
  assert(b >= 0);
  Modular<T> x = a, res = 1;
  U p = b;
  while (p > 0) {
    if (p & 1) res *= x;
    x *= x;
    p >>= 1;
  }
  return res;
}
template <typename T>
bool IsZero(const Modular<T>& number) {
  return number() == 0;
}
template <typename T>
string to_string(const Modular<T>& number) {
  return to_string(number());
}
template <typename T>
std::ostream& operator<<(std::ostream& stream, const Modular<T>& number) {
  return stream << number();
}
template <typename T>
std::istream& operator>>(std::istream& stream, Modular<T>& number) {
  typename common_type<typename Modular<T>::Type, int64_t>::type x;
  stream >> x;
  number.value = Modular<T>::normalize(x);
  return stream;
}
constexpr int md = (int)1e9 + 7;
using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;
vector<Mint> BerlekampMassey(vector<Mint> s) {
  int n = s.size(), L = 0, m = 0;
  vector<Mint> C(n), B(n), T;
  C[0] = B[0] = 1;
  Mint b = 1;
  for (int i = 0; i < n; i++) {
    m++;
    Mint d = s[i];
    for (int j = 1; j <= L; j++) d += C[j] * s[i - j];
    if (!d) continue;
    T = C;
    Mint coef = d / b;
    for (int j = m; j < n; j++) C[j] -= coef * B[j - m];
    if (2 * L <= i) {
      L = i + 1 - L;
      B = T;
      b = d;
      m = 0;
    }
  }
  C.resize(L + 1);
  C.erase(C.begin());
  for (Mint& x : C) x *= -1;
  return C;
}
Mint linearRec(vector<Mint> base, vector<Mint> coef, long long k) {
  int n = coef.size();
  auto combine = [&](vector<Mint> a, vector<Mint> b) {
    vector<Mint> ret(n * 2 + 1);
    for (int i = 0; i <= n; i++)
      for (int j = 0; j <= n; j++) ret[i + j] += a[i] * b[j];
    for (int i = n * 2; i > n; i--)
      for (int j = 0; j < n; j++) ret[i - 1 - j] += ret[i] * coef[j];
    ret.resize(n + 1);
    return ret;
  };
  vector<Mint> r(n + 1), a(n + 1);
  r[0] = a[1] = 1;
  k++;
  while (k) {
    if (k & 1) r = combine(r, a);
    a = combine(a, a);
    k >>= 1;
  }
  Mint ans = 0;
  for (int i = 0; i < n; i++) ans += r[i + 1] * base[i];
  return ans;
}
Mint extrapolate(vector<Mint> p, long long k) {
  vector<Mint> tr = BerlekampMassey(p);
  vector<Mint> base = p;
  base.resize(tr.size());
  return linearRec(base, tr, k);
}
int bad[21][21];
const int nax = 1001;
int dist[nax][nax];
const int drow[8] = {1, 1, -1, -1, 2, 2, -2, -2};
const int dcol[8] = {2, -2, 2, -2, 1, -1, 1, -1};
vector<Mint> brute(int maxdepth) {
  queue<pair<int, int>> q;
  fill_n((int*)dist, nax * nax, 1e9);
  int off = nax / 2;
  dist[off][off] = 0;
  assert(maxdepth * 2 < off);
  vector<Mint> ans(maxdepth + 1);
  ans[0] = 1;
  if (maxdepth) q.emplace(0, 0);
  while (q.size()) {
    auto [row, col] = q.front();
    q.pop();
    int depth = dist[row + off][col + off];
    for (int d = 0; d < 8; d++) {
      int nrow = row + drow[d];
      int ncol = col + dcol[d];
      if (nrow <= 10 && nrow >= -10 && ncol <= 10 && ncol >= -10 &&
          bad[nrow + 10][ncol + 10])
        ;
      else if (dist[nrow + off][ncol + off] == 1e9) {
        dist[nrow + off][ncol + off] = depth + 1;
        ans[depth + 1]++;
        if (depth + 1 < maxdepth) q.emplace(nrow, ncol);
      }
    }
  }
  for (int d = 0; d < maxdepth; d++) ans[d + 1] += ans[d];
  return ans;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  long long k, n;
  cin >> k >> n;
  for (int i = 0; i < n; i++) {
    int x, y;
    cin >> x >> y;
    bad[x + 10][y + 10] = 1;
  }
  cout << extrapolate(brute(200), k) << endl;
}