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:
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

using namespace std;

typedef long double ld;

#ifdef DEBUG
#define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#else
#define eprintf(...) ;
#endif

#define sz(x) ((int) (x).size())
#define TASK "text"

const int inf = (int) 1.01e9;
const long long infll = (long long) 1.01e18;
const ld eps = 1e-9;
const ld pi = acos((ld) -1);

#ifdef DEBUG
mt19937 mrand(300); 
#else
mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count()); 
#endif

int rnd(int x) {
  return mrand() % x;
}

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

int mul(int a, int b) {
  return (long long) a * b % mod;
}

void add(int &a, int b) {
  a += b;
  if (a >= mod) {
    a -= mod;
  }
}

const int inv9 = 111111112;

const int X = (int) 1e5;
int p10[X], p10X[X];

void precalc() {
  p10[0] = 1;
  for (int i = 1; i < X; i++) {
    p10[i] = mul(p10[i - 1], 10);
  }
  p10X[0] = 1;
  p10X[1] = mul(p10[X - 1], 10);
  for (int i = 2; i < X; i++) {
    p10X[i] = mul(p10X[i - 1], p10X[1]);
  }
}

int getP10(int k) {
  return mul(p10X[k / X], p10[k % X]);
}

int n;
vector<pair<int, int>> segs;

bool read() {
  int m;
  if (scanf("%d%d", &n, &m) < 2) {
    return false;
  }
  segs.clear();
  for (int i = 0; i < m; i++) {
    int l, r;
    scanf("%d%d", &l, &r);
    l--;
    segs.push_back(make_pair(l, r));
  }
  return true;
}

vector<int> xs;
vector<int> cid;
vector<int> cs;
vector<pair<int, int>> ops;

void unite(int x, int y) {
  if (cid[x] == cid[y]) {
    return;
  }
  int xid = cid[x], yid = cid[y];
  if (__builtin_popcount(cs[xid]) < __builtin_popcount(cs[yid])) {
    swap(x, y);
    swap(xid, yid);
  }
  for (int i = 0; i < sz(xs); i++) {
    if (cid[i] == yid) {
      ops.push_back(make_pair(i, yid));
      cs[yid] ^= (1 << i);
      cid[i] = xid;
      cs[xid] ^= (1 << i);
    }
  }
}

void rollback(int s) {
  while (sz(ops) > s) {
    int i = ops.back().first, yid = ops.back().second;
    int xid = cid[i];
    cs[xid] ^= (1 << i);
    cid[i] = yid;
    cs[yid] ^= (1 << i);
    ops.pop_back();
  }
}

int rec(int n) {
  if (xs.empty()) {
    return getP10(n);
  }
  int x = xs.back();
  if (n > x) {
    return mul(rec(x), getP10(n - x));
  }
  int id = cid.back();
  int i = sz(xs) - 1;
  if (__builtin_popcount(cs[id]) == 1) {
    xs.pop_back();
    cid.pop_back();
    cs[id] ^= (1 << i);
    int res = rec(n);
    xs.push_back(x);
    cid.push_back(id);
    cs[id] ^= (1 << i);
    return res;
  }
  int j = i - 1;
  while (cid[j] != id) {
    j--;
  }
  if (j == i - 1) {
    int d = xs[i] - xs[j];
    xs.pop_back();
    cid.pop_back();
    cs[id] ^= (1 << i);
    int res = rec(xs[j]);
    xs.push_back(x);
    cid.push_back(id);
    cs[id] ^= (1 << i);
    int tomul = getP10(d);
    add(tomul, mod - 1);
    tomul = mul(tomul, inv9);
    add(tomul, 1);
    res = mul(res, tomul);
    return res;
  }
  int res = 0;
  int d = xs[i] - xs[i - 1];
  xs.pop_back();
  cid.pop_back();
  cs[id] ^= (1 << i);
  {
    int cur = rec(xs[i - 1]);
    int tomul = getP10(d);
    add(tomul, mod - 1);
    tomul = mul(tomul, inv9);
    cur = mul(cur, tomul);
    add(res, cur);
  }
  {
    int s = sz(ops);
    unite(j, i - 1);
    int cur = rec(xs[i - 1]);
    rollback(s);
    add(res, cur);
  }
  xs.push_back(x);
  cid.push_back(id);
  cs[id] ^= (1 << i);
  return res;
}

void solve() {
  xs.clear();
  for (int i = 0; i < sz(segs); i++) {
    xs.push_back(segs[i].first);
    xs.push_back(segs[i].second);
  }
  sort(xs.begin(), xs.end());
  xs.erase(unique(xs.begin(), xs.end()), xs.end());
  for (int i = 0; i < sz(segs); i++) {
    segs[i].first = lower_bound(xs.begin(), xs.end(), segs[i].first) - xs.begin();
    segs[i].second = lower_bound(xs.begin(), xs.end(), segs[i].second) - xs.begin();
  }
  cid = vector<int>(sz(xs));
  cs = vector<int>(sz(xs));
  ops.clear();
  for (int i = 0; i < sz(xs); i++) {
    cid[i] = i;
    cs[i] = (1 << i);
  }
  for (int i = 0; i < sz(segs); i++) {
    unite(segs[i].first, segs[i].second);
  }
  int res = rec(n);
  printf("%d\n", res);
}

int main() {
  precalc();
#ifdef DEBUG
  assert(freopen(TASK ".in", "r", stdin));
  assert(freopen(TASK ".out", "w", stdout));
#endif
  while (read()) {
    solve();
#ifdef DEBUG
    eprintf("Time %.2f\n", (double) clock() / CLOCKS_PER_SEC);
#endif
  }
  return 0;
}