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 N = 15, M = 50, p = 1e9 + 7;
int n, q, idcnt, con[1 << N | 10], f[10][1 << N | 10];
int limcnt, px[M], py[M], pz[M];
map<int, int> fa, id;
inline int Qmi(int x, int y = p - 2) {
    int ans = 1;
    for (; y; y >>= 1, x = 1ll * x * x % p) if (y & 1) ans = 1ll * ans * x % p;
    return ans;
}
inline int Ask(int x) {
    return fa.count(x) ? fa[x] = Ask(fa[x]) : x;
}
vector<int> g;
int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1, x, y; i <= q; ++i) {
        scanf("%d%d", &x, &y); ++y;
        g.push_back(x); g.push_back(y);
        x = Ask(x); y = Ask(y);
        if (x != y) fa[max(x, y)] = min(x, y);
    }
    sort(g.begin(), g.end());
    g.erase(unique(g.begin(), g.end()), g.end());
    const int inv9 = Qmi(9);
    int ans = 1, la = 0;
    for (auto i: g) {
        int val = 1ll * (Qmi(10, i - la) - 1) * inv9 % p;
        ans = 1ll * ans * val % p;
        if (!fa.count(i)) id[i] = idcnt++; else id[i] = id[Ask(i)];
        px[++limcnt] = id[i]; py[limcnt] = id[la]; pz[limcnt] = 1ll * (val + 1) * Qmi(val) % p;
        la = i;
    }
    ans = 1ll * ans * Qmi(10, n + 1 - la) % p * Qmi(10) % p;
    int s = 1 << idcnt;
    for (int i = 0; i < s; ++i) {
        con[i] = 1;
        for (int j = 2; j <= limcnt; ++j)
            if ((i >> px[j] & 1) && (i >> py[j] & 1))
                con[i] = 1ll * con[i] * pz[j] % p;
        f[0][i] = con[i];
        if ((i >> px[1] & 1)) f[0][i] = 1ll * f[0][i] * pz[1] % p;
    }
    for (int cl = 0; cl < 8; ++cl)
        for (int i = 0; i < s; ++i) if (f[cl][i])
            for (int j = i; j < s; j = (j + 1) | i)
                f[cl + 1][j] = (f[cl + 1][j] + 1ll * f[cl][i] * con[i ^ j]) % p;
    ans = (1ll * f[8][s - 1] * ans % p + p) % p;
    printf("%d\n", ans);
    return 0;
}