Problem: Count the number of strings S that satisfy the following constraints, modulo 10^9 + 7.

* The length of S is exactly N.
* S consists of digits (`0`...`9`).
* You are given Q intervals. For each i (1 \leq i \leq Q), the integer represented by S[l_i \ldots r_i] (the substring of S between the l_i-th (1-based) character and the r_i-th character, inclusive) must be a multiple of 9.



Here, the string S and its substrings may have leading zeroes. For example, `002019` represents the integer 2019.

Constraints

* 1 \leq N \leq 10^9
* 1 \leq Q \leq 15
* 1 \leq l_i \leq r_i \leq N

Input

Input is given from Standard Input in the following format:


N
Q
l_1 r_1
:
l_Q r_Q


Output

Print the number of strings that satisfy the conditions, modulo 10^9 + 7.

Examples

Input

4
2
1 2
2 4


Output

136


Input

6
3
2 5
3 5
1 3


Output

2720


Input

20
10
2 15
5 6
1 12
7 9
2 17
5 15
2 4
16 17
2 12
8 17


Output

862268030

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) << ' ' <<

using namespace std;

const int MOD = (int)1e9 + 7;

int Pow(int b, int e) {
  if (e < 0) e += MOD - 1;
  int ret = 1;
  while (e) {
    if (e & 1) ret = 1LL * ret * b % MOD;
    b = 1LL * b * b % MOD;
    e >>= 1;
  }
  return ret;
}

const long long INV9 = Pow(9, -1);

int Brute(int min_l, int max_r, int n,
  const vector<int> &v, const vector<pair<int, int>> &interv) {

  int ends = Pow(10, n - max_r);
  int ans = 0;
  map<int, int> color;
  function<void(int)> Back = [&](int step) {
    if (step == (int)v.size()) {
      vector<pair<int, int>> pos;
      for (auto &p : interv) {
        pos.emplace_back(p.first, color[p.first]);
        pos.emplace_back(p.second, color[p.second]);
        if (color[p.first] != color[p.second]) return;
      }
      sort(pos.begin(), pos.end());
      long long res = ends;
      for (int i = 1; i < (int)pos.size(); ++i) {
        long long curr = (Pow(10, pos[i].first - pos[i - 1].first) - 1 + MOD) *
          INV9 % MOD;
        if (pos[i].second == pos[i - 1].second) {
          curr += 1;
        }
        res = res * curr % MOD;
      }
      int mult = (Pow(10, min_l) - 1) * INV9 % MOD;
      if (color[min_l] == 0) ++mult;
      res = 1LL * res * mult % MOD;
      (ans += res) %= MOD;
//      for (auto &p : pos) {
//        dbg() name(p.first) name(p.second) endl;
//      }
//      dbg() endl;
      return;
    }
    for (auto &p : interv) {
      if (p.first < v[step] && p.second < v[step] && color[p.first] != color[p.second])
        return;
    }
    if (v[step] == 0) {
      color[0] = 0;
      Back(step + 1);
      return;
    }
    for (int dig = 0; dig < 9; ++dig) {
      color[v[step]] = dig;
      Back(step + 1);
    }
  };
  Back(0);
  return ans;
}

int Solve(int n, const vector<int> &v, 
  const vector<pair<int, int>> &interv) {

  auto Norm = [&](int x) {
    int pos = lower_bound(v.begin(), v.end(), x) - v.begin();
    assert(v[pos] == x);
    return pos;
  };

  vector<vector<int>> adj(v.size());
  for (auto &p : interv) {
    int x = Norm(p.first), y = Norm(p.second);
    adj[x].emplace_back(y);
    adj[y].emplace_back(x);
  }

  vector<bool> vis(v.size());
  function<void(int, int&)> DFS = [&](int node, int &mask) {
    mask |= 1 << node;
    vis[node] = true;
    for (int &x : adj[node]) {
      if (!vis[x]) {
        DFS(x, mask);
      }
    }
  };

  auto Calc = [&](int len) {
    return 1LL * (Pow(10, len) - 1 + MOD) * INV9 % MOD;
  };

  vector<int> groups;
  for (int i = 0; i < (int)v.size(); ++i) {
    if (!vis[i]) {
      groups.emplace_back();
      DFS(i, groups.back());
    }
  }

  auto GetCoef = [&](int mask) {
    vector<int> pos;
    for (int i = 0; (1 << i) <= mask; ++i) {
      if (mask & (1 << i)) {
        pos.emplace_back(i);
      }
    }
    int coef = 1;
    for (int i = 1; i < (int)pos.size(); ++i) {
      int x = pos[i - 1], y = pos[i];
      if (x + 1 != y) continue;
      int den = Calc(v[y] - v[x]);
      coef = 1LL * coef * Pow(den, -1) % MOD;
      coef = 1LL * coef * (den + 1) % MOD;
    }
    return coef;
  };
  
  int m = groups.size();
  vector<int> coef(1 << m), meta_mask(1 << m);
  for (int meta = 1; meta < (1 << m); ++meta) {
    int &mask = meta_mask[meta];
    for (int i = 0; i < m; ++i) {
      if (meta & (1 << i)) {
        mask |= groups[i];
      }
    }
    coef[meta] = GetCoef(mask);
  }
  
  auto dp = coef; // for color 0
  for (int color = 1; color < 9; ++color) {
    for (int meta = (1 << m) - 1; meta > 0; --meta) {
      for (int sub = (meta - 1) & meta; sub > 0; sub = (sub - 1) & meta) {
        int oth = meta ^ sub;
        // we need to force the prefix sum of no digits to be 0
        if (oth & 1) continue;
        (dp[meta] += 1LL * dp[sub] * coef[oth] % MOD) %= MOD;
      }
    }
  }
  int ans = 1LL * Pow(10, v[0]) * Pow(10, n - v.back()) % MOD;
  for (int i = 1; i < (int)v.size(); ++i) {
    ans = 1LL * ans * Calc(v[i] - v[i - 1]) % MOD;
  }
  ans = 1LL * ans * dp[(1 << m) - 1] % MOD;
  return ans;
}

void Read(int &n, int &q, vector<pair<int, int>> &interv) {
  cin >> n >> q;
  interv.resize(q);
  for (auto &p : interv) {
    cin >> p.first >> p.second; --p.first;
  }
}

void Gen(int &n, int &q, vector<pair<int, int>> &interv) {
  n = 5, q = 4;
  mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  interv.resize(q);
  dbg() n << '\n' << q << endl;
  for (auto &p : interv) {
    p.first = rng() % n + 1;
    p.second = rng() % n + 1;
    if (p.first > p.second) swap(p.first, p.second);
    dbg() p.first << ' ' << p.second << endl;
    --p.first;
  }
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

//  while (true) {
  int n, q;
  vector<pair<int, int>> interv;
  bool gen = false;
  if (gen) {
    Gen(n, q, interv);
  } else {
    Read(n, q, interv);
  }

  vector<int> v(2 * q);
  int min_l = (int)1e9 + 5, max_r = -1;
  for (int i = 0; i < q; ++i) {
    int l, r; tie(l, r) = interv[i];
    min_l = min(min_l, l);
    max_r = max(max_r, r);
    v[i] = l;
    v[i + q] = r;
  }
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());

#ifdef LOCAL_DEFINE
  int correct_answer = Brute(min_l, max_r, n, v, interv);
#endif

  int ans = Solve(n, v, interv);
  cout << ans << endl;
  
#ifdef LOCAL_DEFINE
  if (ans != correct_answer) {
    cout << correct_answer << endl;
    throw;
  }
#endif
//  }
}