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<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<iostream>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include<bitset>
#include<vector>
#include<limits.h>
#include<assert.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define FOR(I, A, B) for (int I = (A); I <= (B); ++I)
#define FORS(I, S) for (int I = 0; S[I]; ++I)
#define RS(X) scanf("%s", (X))
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define CASET int ___T; scanf("%d", &___T); for(int cs=1;cs<=___T;cs++)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<PII> VPII;
typedef pair<LL,LL> PLL;
typedef vector<PLL> VPLL;
template<class T> void _R(T &x) { cin >> x; }
void _R(int &x) { scanf("%d", &x); }
void _R(LL &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); }
template<class T> void _W(const T &x) { cout << x; }
void _W(const int &x) { printf("%d", x); }
void _W(const LL &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template<class T,class U> void _W(const pair<T,U> &x) {_W(x.F); putchar(' '); _W(x.S);}
template<class T> void _W(const vector<T> &x) { for (auto i = x.begin(); i != x.end(); _W(*i++)) if (i != x.cbegin()) putchar(' '); }
void W() {}
template<class T, class... U> void W(const T &head, const U &... tail) { _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); W(tail...); }
#ifdef HOME
 #define DEBUG(...) {printf("# ");printf(__VA_ARGS__);puts("");}
#else
 #define DEBUG(...)
#endif
int MOD = 1e9+7;
void ADD(LL& x,LL v){x+=v;if(x>=MOD)x-=MOD;}
/*}}}*/
const int SIZE = 30;
LL mypow(LL x,LL y){
    x%=MOD;
    LL res=1%MOD;
    while(y){
        if(y&1)res=res*x%MOD;
        y>>=1;
        x=x*x%MOD;
    }
    return res;
}
void my_mul(LL &x,LL v){x=x*v%MOD;}
int get_bit(int x,int v){
    return (x>>v)&1;
}
LL ten[33],one[33];
void init(){
    ten[0]=10;
    one[0]=1;
    REPP(i,1,33){
        ten[i]=ten[i-1]*ten[i-1]%MOD;
        one[i]=(one[i-1]*ten[i-1]+one[i-1])%MOD;
    }
}
LL eleven(int n){
    LL now=0;
    for(int i=0;n>>i;i++){
        if(get_bit(n,i)){
            now=(now*ten[i]+one[i])%MOD;
        }
    }
    return now;
}
int AA[SIZE];
VI aa[SIZE];
int type_num;
int e[SIZE][2];
int d[SIZE],dn;
int ee[SIZE];
int id[SIZE];
int ty[SIZE];
int N,Q;
LL mul[SIZE],mulmul[SIZE];
VI order,unorder;
LL dfs(int x,LL now,int num){
    if(x==SZ(order)){
        for(int y:unorder){
            LL val[9]={};
            fill(val,val+9,1);
            LL for_all=1;
            for(int pos:aa[y]){
                if(pos&&id[pos-1]!=id[pos]){
                    my_mul(for_all,mul[pos]);
                    my_mul(val[ty[id[pos-1]]],mulmul[pos]);
                }
                if(pos+1<dn&&id[pos+1]!=id[pos]){
                    my_mul(for_all,mul[pos+1]);
                    my_mul(val[ty[id[pos+1]]],mulmul[pos+1]);
                }
            }
            LL ss=0;
            REP(i,9){
                ADD(ss,val[i]);
            }
            my_mul(now,ss*for_all%MOD);
        }
        return now;
    }
    LL sum=0;
    VL val2(num+1);
    fill(ALL(val2),1);
    for(int pos:aa[order[x]]){
        if(pos&&id[pos-1]!=id[pos]&&ty[id[pos-1]]!=-1){
            my_mul(now,mul[pos]);
            my_mul(val2[ty[id[pos-1]]],mulmul[pos]);
        }
        if(pos+1<dn&&id[pos+1]!=id[pos]&&ty[id[pos+1]]!=-1){
            my_mul(now,mul[pos+1]);
            my_mul(val2[ty[id[pos+1]]],mulmul[pos+1]);
        }
    }
    FOR(v,0,num){
        ty[order[x]]=v;
        if(v==num){
            if(num<9) ADD(sum,dfs(x+1,now*val2[v]%MOD*(9-num)%MOD,num+1));
        }
        else {
            ADD(sum,dfs(x+1,now*val2[v]%MOD,num));
        }
    }
    ty[order[x]]=-1;
    return sum;
}
int main(){
    init();R(N,Q);
    REP(i,Q){
        int x,y;
        R(x,y);
        x--;
        e[i][0]=x;
        e[i][1]=y;
        d[dn++]=x;
        d[dn++]=y;
    }
    sort(d,d+dn);
    dn=unique(d,d+dn)-d;
    REPP(i,1,dn){
        mul[i]=eleven(d[i]-d[i-1]);
        mulmul[i]=(mul[i]+1)*mypow(mul[i],MOD-2)%MOD;
    }
    REP(i,Q){
        REP(j,2)e[i][j]=lower_bound(d,d+dn,e[i][j])-d;
        ee[e[i][0]]|=1<<e[i][1];
        ee[e[i][1]]|=1<<e[i][0];
    }
    REP(k,dn)REP(i,dn)REP(j,dn){
        if(get_bit(ee[i],k)&&get_bit(ee[k],j))ee[i]|=1<<j;
    }
    LL base=mypow(10,d[0]+N-d[dn-1]);
    int good_mask;
    {
        int need=0;
        REP(i,dn-1){
            if(!get_bit(ee[i],i+1))need|=1<<i;
            else my_mul(base,mul[i+1]+1);
        }
        int tmp=0;
        bool u[SIZE]={};
        REP(i,dn){
            if(!u[i]){
                REP(j,dn){
                    if(get_bit(ee[i],j)||i==j){
                        AA[tmp]|=1<<j;
                        aa[tmp].PB(j);
                        u[j]=1;
                        id[j]=tmp;
                    }
                }
                tmp++;
            }
        }
        type_num=tmp;
        int mi=100;
        for(int i=1;i<(1<<type_num);i++){
            int me=0;
            REP(j,type_num){
                if(get_bit(i,j))me|=AA[j]|(AA[j]>>1);
            }
            if((need&me)==need){
                int bn=__builtin_popcount(i);
                if(bn<mi){
                    mi=bn;
                    good_mask=i;
                }
            }
        }
        REP(i,type_num){
            if(get_bit(good_mask,i))order.PB(i);
            else unorder.PB(i);
        }
    }
    MS1(ty);
    ty[order[0]]=0;
    W(dfs(1,1,1)*base%MOD);
    return 0;
}