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>

using namespace std;
const int kMod = 1e9 + 7;

int Pow(int b, int e) {
  int res = 1;
  while (e) {
    if (e % 2) res = 1LL * res * b % kMod;
    b = 1LL * b * b % kMod;
    e /= 2;
  }
  return res;
}
int Inv(int x) {
  return Pow(x, kMod - 2);
}
int Compute(int n) {
  return 1LL * (Pow(10, n) - 1) * Inv(9) % kMod;
}

int main() {
  int n, q; cin >> n >> q;

  vector<pair<int, int>> cons;
  vector<int> all = {0, n};
  for (int i = 0; i < q; ++i) {
    int a, b; cin >> a >> b;
    cons.emplace_back(a - 1, b);
    all.push_back(a - 1);
    all.push_back(b);
  }
  
  sort(all.begin(), all.end());
  all.erase(unique(all.begin(), all.end()), all.end());
  auto get = [&](int x) {
    auto it = lower_bound(all.begin(), all.end(), x);
    assert(it != all.end() && *it == x);
    return it - all.begin();
  };

  for (int i = 0; i < q; ++i) {
    cons[i].first = get(cons[i].first);
    cons[i].second = get(cons[i].second);
  }

  vector<bool> vis(all.size(), 0);
  int msk = 0;
  function<void(int)> dfs = [&](int node) {
    vis[node] = true;
    msk |= (1 << node);
    for (auto p : cons) {
      if (p.first == node && !vis[p.second])
        dfs(p.second);
      if (p.second == node && !vis[p.first])
        dfs(p.first);
    }
  };
  
  vector<int> delta(all.size(), 0);
  for (int i = 1; i < (int)all.size(); ++i) {
    delta[i] = Compute(all[i] - all[i - 1]);
  }
  
  int coef = 1;
  vector<int> masks;
  for (int i = 0; i < (int)all.size(); ++i) {
    if (!vis[i]) {
      msk = 0;
      dfs(i);
      if (i != 0 && msk == (1 << i)) {
        coef = 1LL * coef * Pow(10, all[i] - all[i - 1]) % kMod;
      } else {
        masks.push_back(msk);
      }
    }
  }

  n = masks.size();
  vector<int> add(1 << n, 0), mskmem(1 << n, 0);
  for (int s = 0; s < (1 << n); ++s) {
    int msk = 0;
    for (int i = 0; i < n; ++i) {
      if (!(s & (1 << i))) continue;
      msk |= masks[i]; 
    }
    mskmem[s] = msk;

    int coef = 1;
    for (int i = 0; i < (int)all.size(); ++i) {
      if (!(msk & (1 << i))) continue;
      if (i == 0) continue;

      int now = delta[i];
      if (msk & (1 << (i - 1))) now += 1;
      coef = 1LL * coef * now % kMod;
    }
    add[s] = coef;
  }
  /*  
  cerr << "delta: ";
  for (auto x : delta) 
    cerr << x << " "; 
  cerr << endl;

  for (int i = 0; i < n; ++i) {
    cerr << "set " << i << ": ";
    for (int j = 0; j < (int)all.size(); ++j) {
      if (masks[i] & (1 << j))
        cerr << all[j] << " ";
    }
    cerr << endl;
  }
  
  for (int i = 0; i < (1 << n); ++i) {
    cerr << add[i] << " ";
  }
  cerr << endl;
  */
  vector<int> dp(1 << n, 0);
  dp[0] = 1;
  for (int dig = 0; dig <= 8; ++dig) {
    for (int s = (1 << n) - 1; s >= 0; --s) {
      for (int sub = s; sub > 0; sub = ((sub - 1) & s)) {
        int msk = mskmem[sub];
        if ((msk & 1) != (dig == 0)) continue;
        dp[s] = (dp[s] + 1LL * dp[sub ^ s] * add[sub]) % kMod;
      }
    }
  }

  int ret = 1LL * dp[(1 << n) - 1] * coef % kMod;
  if (ret < 0) ret += kMod;
  cout << ret << endl;
  
  return 0;
}