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 mod = 1e9 + 7, N = 16;

namespace {
  inline int add(int x, int y) { return (x += y) >= mod ? x - mod : x; }
  inline int sub(int x, int y) { return (x -= y) < 0 ? x + mod : x; }
  inline int mul(int x, int y) { return 1LL * x * y % mod; }
  inline int kissme(int x, int y) {
    int c = 1;
    while(y) {
      if(y & 1) {
	c = mul(c, x);
      }
      x = mul(x, x);
      y >>= 1;
    }
    return c;
  }
}

int n, Q, scnt, l[N], r[N], h[1 << N], f[10][1 << N];
bool vis[N << 1];
vector<int> all, vec[N], g[N << 1];

int get(int x) {
  if(!x) {
    return 1;
  }
  return mul(sub(kissme(10, x), 1), kissme(9, mod - 2));
}

int calc(vector<int> a) {
  sort(a.begin(), a.end());
  int ans = 1;
  for(int i = 1; i < a.size(); i++) {
    if(a[i] - a[i - 1] == 1) {
      int x = get(all[a[i]] - all[a[i - 1]]);
      ans = mul(ans, mul(add(x, 1), kissme(x, mod - 2)));
    }
  }
  return ans;
}

void dfs(int s, int x) {
  vis[x] = true;
  vec[s].push_back(x);
  for(int v : g[x]) {
    if(!vis[v]) {
      dfs(s, v);
    }
  }
}

int main(void) {
  scanf("%d%d", &n, &Q);
  for(int i = 1; i <= Q; i++) {
    scanf("%d%d", &l[i], &r[i]);
    l[i]--;
    all.push_back(l[i]);
    all.push_back(r[i]);
  }
  sort(all.begin(), all.end());
  all.erase(unique(all.begin(), all.end()), all.end());
  for(int i = 1; i <= Q; i++) {
    l[i] = lower_bound(all.begin(), all.end(), l[i]) - all.begin();
    r[i] = lower_bound(all.begin(), all.end(), r[i]) - all.begin();
    g[l[i]].push_back(r[i]);
    g[r[i]].push_back(l[i]);
  }
  for(int i = 0; i < all.size(); i++) {
    if(!vis[i]) {
      dfs(scnt++, i);
    }
  }
  for(int i = 0; i < (1 << scnt); i++) {
    vector<int> cur;
    for(int j = 0; j < scnt; j++) {
      if(i >> j & 1) {
	for(int k : vec[j]) {
	  cur.push_back(k);
	}
      }
    }
    h[i] = calc(cur);
  }
  f[0][0] = 1;
  for(int o = 0; o < 9; o++) {
    for(int i = 0; i < (1 << scnt); i++) {
      if(!f[o][i]) {
	continue;
      }
      int t = (1 << scnt) - 1 - i;
      for(int j = t; ; j = t & (j - 1)) {
	f[o + 1][i | j] = add(f[o + 1][i | j], mul(f[o][i], h[j]));
	if(!j) {
	  break;
	}
      }
    }
  }
  int ans = mul(f[9][(1 << scnt) - 1], kissme(10, all[0]));
  for(int i = 1; i < all.size(); i++) {
    ans = mul(ans, get(all[i] - all[i - 1]));
  }
  cout << mul(mul(ans, kissme(10, n - all.back())), kissme(9, mod - 2)) << endl;
  return 0;
}