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 <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <numeric>

const int MOD = (int)1e9 + 7;
int n, q, l[15], r[15];
int mask[15];
int dsu[15];

int inv(int x) {
  return x == 1 ? 1 : (MOD - MOD / x) * 1LL * inv(MOD % x) % MOD;
}

int find(int x) {
  return dsu[x] == x ? x : dsu[x] = find(dsu[x]);
}

int power(int a, int b) {
  int ret = 1;
  for ( ; b; b >>= 1, a = a * 1LL * a % MOD) if (b & 1) ret = ret * 1LL * a % MOD;
  return ret;
}

int main() {
  scanf("%d%d", &n, &q);
  std::vector<int> ss{0};
  for (int i = 0; i < q; ++ i) {
    scanf("%d%d", l + i, r + i);
    ss.emplace_back(l[i] - 1);
    ss.emplace_back(r[i]);
  }
  std::sort(ss.begin(), ss.end());
  ss.erase(std::unique(ss.begin(), ss.end()), ss.end());
  std::iota(dsu, dsu + q, 0);
  auto get = [&ss](int x) -> int {
    return std::lower_bound(ss.begin(), ss.end(), x) - ss.begin();
  };
  for (int i = 0; i < q; ++ i) {
    mask[i] = 1 << get(l[i] - 1) | 1 << get(r[i]);
  }
  for (int i = 0; i < q; ++ i) {
    for (int j = i + 1; j < q; ++ j) {
      int a = find(i), b = find(j);
      if (a != b && (mask[a] & mask[b])) {
        mask[a] |= mask[b];
        dsu[b] = a;
      }
    }
  }
  std::vector<int> groups;
  for (int i = 0; i < q; ++ i) if (dsu[i] == i) groups.emplace_back(mask[i]);
  int m = groups.size();
  const int inv9 = inv(9);
  auto calc = [&](int at, bool eq) {
    if (at == 0) return 1;
    int e = (power(10, ss[at] - ss[at - 1]) + MOD - 1) % MOD * 1LL * inv9 % MOD;
    if (eq) e = (e + 1) % MOD;
    return e;
  };

  std::vector<std::vector<int>> coef(2, std::vector<int>(1 << m));
  for (int w = 0; w < 1 << m; ++ w) {
    for (int o = 0; o < 2; ++ o) {
      int msk = o == 1;
      for (int i = 0; i < m; ++ i) if (w >> i & 1) msk |= groups[i];
      int ways = 1;
      for (int i = 0; msk >> i; ++ i) if (msk >> i & 1) {
        ways = ways * 1LL * calc(i, i && (msk >> i - 1 & 1)) % MOD;
      }
      coef[o][w] = ways;
    }
  }
  std::vector<std::vector<int>> dp(10, std::vector<int>(1 << m));
  dp[0][0] = 1;
  int p = -1;
  for (int i = 0; i < m; ++ i)
    if (groups[i] & 1)
      p = i;
  for (int i = 0; i < 9; ++ i) {
    for (int w = 0; w < 1 << m; ++ w) {
      for (int b = w; ; b = b - 1 & w) {
        if (i == 0 || p == -1 || (~b >> p & 1)) {
          dp[i + 1][w] = (dp[i + 1][w] + coef[i == 0][b] * 1LL * dp[i][w ^ b] % MOD) % MOD;
        }
        if (b == 0) break;
      }
    }
  }
  int result = dp[9][(1 << m) - 1] * 1LL * power(10, n - ss.back()) % MOD;
  printf("%d\n", result);
}