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 md = 1e9 + 7;

inline void add(int &x, int y) {
  x += y;
  if (x >= md) {
    x -= md;
  }
}

inline int mul(int x, int y) {
  return (int) ((long long) x * y % md);
}

inline int power(int x, int y) {
  int res = 1;
  while (y) {
    if (y & 1) {
      res = mul(res, x);
    }
    x = mul(x, x);
    y >>= 1;
  }
  return res;
}

inline int inv(int a) {
  int b = md, u = 0, v = 1;
  while (a) {
    int t = b / a;
    b -= t * a;
    swap(a, b);
    u -= t * v;
    swap(u, v);
  }
  if (u < 0) {
    u += md;
  }
  return u;
}

int main() {
#ifdef wxh010910
  freopen("input.txt", "r", stdin);
#endif
  int n, m;
  cin >> n >> m;
  vector<pair<int, int>> segments;
  segments.emplace_back(0, 0);
  for (int i = 0; i < m; ++i) {
    int l, r;
    cin >> l >> r;
    segments.emplace_back(l - 1, i + 1);
    segments.emplace_back(r, i + 1);
  }
  sort(segments.begin(), segments.end());
  ++m;
  vector<vector<pair<int, int>>> extra(m);
  vector<int> adj(m);
  int ans = 1, inv9 = inv(9);
  for (int i = 1; i < (int) segments.size(); ++i) {
    int x = segments[i - 1].second, y = segments[i].second;
    if (segments[i - 1].first == segments[i].first) {
      adj[x] |= 1 << y;
      adj[y] |= 1 << x;
    } else {
      int base = mul(inv9, power(10, segments[i].first - segments[i - 1].first) - 1);
      ans = mul(ans, base);
      base = mul(base + 1, inv(base));
      extra[x].emplace_back(y, base);
    }
  }
  ans = mul(ans, power(10, n - segments.back().first));
  vector<int> coef(1 << m);
  for (int i = 0; i < 1 << m; ++i) {
    coef[i] = 1;
    for (int j = 0; j < m; ++j) {
      if (i >> j & 1) {
        if ((adj[j] & i) != adj[j]) {
          coef[i] = 0;
          break;
        }
        for (auto p : extra[j]) {
          if (i >> p.first & 1) {
            coef[i] = mul(coef[i], p.second);
          }
        }
      }
    }
  }
  vector<int> dp(1 << m);
  dp[0] = 1;
  for (int group = 0; group < 9; ++group) {
    vector<int> new_dp(1 << m);
    for (int i = 0; i < 1 << m; ++i) {
      if (dp[i]) {
        int subset = ((1 << m) - 1) ^ i;
        for (int j = subset; ; j = (j - 1) & subset) {
          if (group || (j & 1)) {
            add(new_dp[i | j], mul(dp[i], coef[j]));
          }
          if (!j) {
            break;
          }
        }
      }
    }
    swap(dp, new_dp);
  }
  ans = mul(ans, dp.back());
  cout << ans << "\n";
  return 0;
}