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:
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;

//template
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(a);i>(b);i--)
#define ALL(v) (v).begin(),(v).end()
typedef long long int ll; typedef pair<ll, ll> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<typename A,size_t N,typename T>void Fill(A(&array)[N],const T &val){fill((T*)array, (T*)(array+N), val);}
const int inf = 0x3fffffff; const ll INF = 0x3fffffffffffffff;
//template end

ll mod=1e9+7;
struct Mint {
    ll val;
    Mint inv() const{
        ll tmp,a=val,b=mod,x=1,y=0;
        while(b)tmp=a/b,a-=tmp*b,swap(a,b),x-=tmp*y,swap(x,y);
        return Mint(x);
    }
public:
    Mint():val(0){}
    Mint(ll x):val(x>=0?x%mod:x%mod+mod){}
    int mtoi(){return this->val; }
    Mint pow(ll t){Mint res=1,b=*this; while(t){if(t&1)res*=b;b*=b;t>>=1;}return res;}
    Mint& operator+=(const Mint& x){if((val+=x.val)>=mod)val-=mod;return *this;}
    Mint& operator-=(const Mint& x){if((val+=mod-x.val)>=mod)val-=mod; return *this;}
    Mint& operator*=(const Mint& x){val=(ll)val*x.val%mod; return *this;}
    Mint& operator/=(const Mint& x){return *this *= x.inv();}
    bool operator==(const Mint& x) const{return val == x.val;}
    bool operator!=(const Mint& x) const{return val != x.val;}
    bool operator<(const Mint& x) const{return val < x.val;}
    bool operator<=(const Mint& x) const{return val <= x.val;}
    bool operator>(const Mint& x) const{return val > x.val;}
    bool operator>=(const Mint& x) const{return val >= x.val;}
    Mint operator+(const Mint& x) const{return Mint(*this)+=x;}
    Mint operator-(const Mint& x) const{return Mint(*this)-=x;}
    Mint operator*(const Mint& x) const{return Mint(*this)*=x;}
    Mint operator/(const Mint& x) const{return Mint(*this)/=x;}
};
struct factorial {
    vector<Mint> Fact, Finv;
public:
    factorial(int maxx){
        Fact.resize(maxx+1),Finv.resize(maxx+1); Fact[0]=Mint(1); rep(i,0,maxx)Fact[i+1]=Fact[i]*Mint(i+1);
        Finv[maxx]=Mint(1)/Fact[maxx]; rrep(i,maxx,0)Finv[i-1]=Finv[i]*Mint(i);
    }
    Mint fact(int n,bool inv=0){if(inv)return Finv[n];else return Fact[n];}
    Mint nPr(int n,int r){if(n<0||n<r||r<0)return Mint(0);else return Fact[n]*Finv[n-r];}
    Mint nCr(int n,int r){if(n<0||n<r||r<0)return Mint(0);else return Fact[n]*Finv[r]*Finv[n-r];}
};

template<class Abel> struct UnionFind {
    vector<int> par,rank;
    vector<Abel> diff_weight;
    UnionFind(int n=1,Abel SUM_UNITY=0){init(n, SUM_UNITY);}
    void init(int n=1,Abel SUM_UNITY=0) {
        par.resize(n); rank.resize(n); diff_weight.resize(n);
        rep(i,0,n)par[i]=i,rank[i]=0,diff_weight[i]=SUM_UNITY;
    }
    int root(int x){
        if(par[x]==x)return x;
        int r=root(par[x]); diff_weight[x]+=diff_weight[par[x]];
        return par[x]=r;
    }
    Abel weight(int x){root(x); return diff_weight[x];}
    bool issame(int x, int y){return root(x)==root(y);}
    bool merge(int x,int y,Abel w){
        w+=weight(x)-weight(y); x=root(x); y=root(y);
        if(x==y)return false;
        if(rank[x]<rank[y])swap(x,y),w=-w;
        if(rank[x]==rank[y])++rank[x];
        par[y]=x; diff_weight[y]=w; return true;
    }
    Abel diff(int x,int y){return weight(y)-weight(x);}
};

Mint coeff[1<<16],dp[11][1<<16];

int main(){
    int n,q; scanf("%d%d",&n,&q);
    int l[20],r[20];
    rep(i,0,q)scanf("%d%d",&l[i],&r[i]),l[i]--;
    vector<int> val; map<int,int> rev;
    rep(i,0,q)val.push_back(l[i]),val.push_back(r[i]);
    sort(ALL(val)); val.erase(unique(ALL(val)),val.end());
    rep(i,0,val.size())rev[val[i]]=i;
    UnionFind<int> uni(q);
    rep(i,0,q)rep(j,i+1,q)if(l[i]==l[j]||l[i]==r[j]||r[i]==l[j]||r[i]==r[j])uni.merge(i,j,1);
    vector<vector<int>> equal;
    rep(i,0,q)if(uni.root(i)==i){
        vector<int> add;
        rep(j,0,q)if(uni.root(j)==i){
            add.push_back(rev[l[j]]);
            add.push_back(rev[r[j]]);
        }
        sort(ALL(add)); add.erase(unique(ALL(add)),add.end());
        equal.push_back(add);
    }
    q=equal.size(); Fill(coeff,Mint(1));
    rep(mask,0,1<<q){
        vector<int> idxs;
        rep(i,0,q)if(mask>>i&1)for(int idx:equal[i])idxs.push_back(idx);
        if(idxs.empty())continue; sort(ALL(idxs));
        rep(i,0,idxs.size()-1)if(idxs[i]+1==idxs[i+1]){
            Mint mul=(Mint(10).pow(val[idxs[i+1]]-val[idxs[i]])-1)/9;
            coeff[mask]*=(mul+1)/mul;
        }
    }
    dp[0][0]=1;
    rep(i,0,9)rep(mask,0,1<<q){
        for(int sub=mask;;sub=(sub-1)&mask){
            dp[i+1][mask]+=dp[i][mask^sub]*coeff[sub];
            if(sub==0)break;
        }
    }
    Mint ans=dp[9][(1<<q)-1];
    rep(i,0,val.size()-1)ans*=(Mint(10).pow(val[i+1]-val[i])-1)/9;
    ans*=Mint(10).pow(val.front()+n-val.back())/9;
    printf("%d\n",ans.mtoi());
    return 0;
}