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;

struct UnionFind {
    vector<int> par;
    vector<int> sz;

    UnionFind(int n=0){
        if(n>0) initialize(n);
    }

    void initialize(int n){
        par.resize(n);
        sz.resize(n);
        for(int i=0; i<n; i++){
            par[i] = i;
            sz[i] = 1;
        }
    }

    int find(int x){
        if(par[x] == x){
            return x;
        }else{
            return par[x] = find(par[x]);
        }
    }

    void unite(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y) return;
        if(sz[x] < sz[y]){
            par[x] = y;
            sz[y] += sz[x];
        }else{
            par[y] = x;
            sz[x] += sz[y];
        }
    }

    bool same(int x, int y){
        return find(x) == find(y);
    }
};

int nth_bit(int64_t num, int n){
    return (num >> n) & 1;
}

const int64_t MOD = 1e9+7;
void add(int64_t& a, int64_t b){
    a = (a+b) % MOD;
}
void mul(int64_t& a, int64_t b){
    a = a*b % MOD;
}

int64_t power_mod(int64_t num, int64_t power){
    int64_t prod = 1;
    num %= MOD;
    while(power > 0){
        if(power&1) prod = prod * num % MOD;
        num = num * num % MOD;
        power >>= 1;
    }
    return prod;
}

int64_t extgcd(int64_t a, int64_t b, int64_t& x, int64_t& y){
    int64_t d = a;
    if(b != 0){
        d = extgcd(b, a%b, y, x);
        y -= (a/b) * x;
    }else{
        x = 1; y = 0;
    }
    return d;
}

int64_t inv_mod(int64_t a){
    int64_t x, y;
    extgcd(a, MOD, x, y);
    return (MOD + x%MOD) % MOD;
}

int main(){
    int N, Q, L[15], R[15];
    cin >> N >> Q;
    for(int i=0; i<Q; i++){
        cin >> L[i] >> R[i];
        L[i]--;
    }

    // しておいたほうが便利なので座標圧縮
    vector<int> compress;
    for(int i=0; i<Q; i++){
        compress.push_back(L[i]);
        compress.push_back(R[i]);
    }
    sort(compress.begin(), compress.end());
    compress.erase(unique(compress.begin(), compress.end()), compress.end());
    map<int, int> compress_inv;
    for(int i=0; i<compress.size(); i++) compress_inv[compress[i]] = i;
    
    // 同じ累積和を持つクエリを結合しておく
    UnionFind uf(Q);
    for(int i=0; i<Q; i++) for(int j=i+1; j<Q; j++){
        if(L[i] == L[j] || L[i] == R[j] || R[i] == L[j] || R[i] == R[j]) uf.unite(i, j);
    }

    // それぞれの条件式グループごとに、そのグループに含まれる累積和を座標圧縮後のindexで格納する
    vector<vector<int>> components;
    for(int i=0; i<Q; i++){
        if(uf.find(i) != i) continue;
        vector<int> v;
        for(int j=0; j<Q; j++){
            if(uf.same(i, j)){
                v.push_back(compress_inv[L[j]]);
                v.push_back(compress_inv[R[j]]);
            }
        }
        sort(v.begin(), v.end());
        v.erase(unique(v.begin(), v.end()), v.end());
        components.push_back(v);
    }
    sort(components.begin(), components.end());
    Q = components.size();

    // それぞれのグループについて「そのグループの値が同じときに得られる係数」を前計算
    static int64_t coefficients[1<<15];
    for(int bits=0; bits<(1<<Q); bits++){
        vector<int> pts;
        for(int i=0; i<Q; i++) if(nth_bit(bits, i)){
            for(int v : components[i]) pts.push_back(v);
        }
        sort(pts.begin(), pts.end());

        int64_t c = 1;
        for(int i=0; i<(int)pts.size()-1; i++){
            if(pts[i]+1 == pts[i+1]){
                int dist = compress[pts[i+1]] - compress[pts[i]];
                int64_t val = power_mod(10, dist) - 1;
                mul(c, (val+9) * inv_mod(val) % MOD);
            }
        }
        coefficients[bits] = c;
    }

    // 部分集合列挙DP
    static int64_t dp[10][1<<15];
    dp[0][0] = 1;
    for(int n=1; n<=9; n++){
        for(int bits=0; bits<(1<<Q); bits++){
            for(int use=bits; use>=0; use=(use-1)&bits){
                // 一番左にある累積和は1つの値（ここでは1）に固定されている、と考える
                if(nth_bit(use, 0) && n != 1) continue;

                int64_t result = dp[n-1][bits-use] * coefficients[use] % MOD;
                add(dp[n][bits], result);
                if(use == 0) break;
            }
        }
    }

    int64_t ans = dp[9][(1<<Q)-1];

    // 最後に全体に掛かる係数もろもろを掛ける
    for(int i=0; i<compress.size()-1; i++){
        int dist = compress[i+1] - compress[i];
        int64_t result = (power_mod(10, dist) - 1 + MOD) * inv_mod(9) % MOD;
        mul(ans, result);
    }
    mul(ans, power_mod(10, compress[0]));
    mul(ans, power_mod(10, N - compress.back()));

    cout << ans << endl;
    return 0;
}