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 <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
const ll MOD=1e9+7;
vector<vector<ll>> matrixmul(int l, int m, int n, vector<vector<ll>> a, vector<vector<ll>> b){
	vector<vector<ll>> c;
	for(int i=0; i<l; i++){
		vector<ll> v;
		for(int j=0; j<n; j++){
			ll x=0;
			for(int k=0; k<m; k++){
				x+=(a[i][k]*b[k][j]);
				x%=MOD;
			}
			v.push_back(x);
		}
		c.push_back(v);
	}
	return c;
}
vector<vector<ll>> matrixpow(int n, vector<vector<ll>> a, ll k){
	vector<vector<ll>> ap=a, ans;
	for(int i=0; i<n; i++){
		vector<ll> v;
		for(int j=0; j<n; j++){
			if(i==j){
				v.push_back(1);
			}else{
				v.push_back(0);
			}
		}
		ans.push_back(v);
	}
	while(k){
		if(k&1) ans=matrixmul(n, n, n, ap, ans);
		ap=matrixmul(n, n, n, ap, ap);
		k>>=1;
	}
	return ans;
}
ll calc(int x){
    vector<vector<ll>> a;
    for(int i=0; i<9; i++){
        vector<ll> a1;
        for(int j=0; j<9; j++){
            if(i==j) a1.push_back(2);
            else a1.push_back(1);
        }
        a.push_back(a1);
    }
    vector<vector<ll>> ans=matrixpow(9, a, x);
    return ans[0][0];
}
ll powmod(ll a, ll k){
    ll ap=a, ans=1;
    while(k){
        if(k&1){
            ans*=ap;
            ans%=MOD;
        }
        ap=ap*ap;
        ap%=MOD;
        k>>=1;
    }
    return ans;
}
ll inv(ll a){
	return powmod(a, MOD-2);
}
int main()
{
    ll n; cin>>n;
    int q; cin>>q;
    int l[16], r[16];
    map<int, int> mp;
    for(int i=0; i<q; i++){
        cin>>l[i]>>r[i];
        l[i]--;
        mp[l[i]]=0, mp[r[i]]=0;
    }
    int m=0;
    int v[32];
    for(auto &p:mp){
        p.second=m; v[m]=p.first; m++;
    }
    for(int i=0; i<q; i++){
        l[i]=mp[l[i]], r[i]=mp[r[i]];
    }
    ll cal[32];
    ll tot=powmod(10, n-v[m-1]+v[0]);
    for(int i=0; i<m-1; i++){
        ll x=calc(v[i+1]-v[i]);
        ll x0=powmod(10, v[i+1]-v[i]);
        ll y=(x0-x+MOD)%MOD*inv(8)%MOD;
        tot*=y; tot%=MOD;
        cal[i]=x*inv(y)%MOD;
    }
    ll c[1<<15];
    for(int i=1; i<(1<<q); i++){
        c[i]=1;
        bool used[32]={};
        for(int j=0; j<q; j++){
            if(i&(1<<j)){
                used[l[j]]=1, used[r[j]]=1;
            }
        }
        for(int j=0; j<m-1; j++){
            if(used[j] && used[j+1]){
                c[i]*=cal[j]; c[i]%=MOD;
            }
        }
    }
    ll dp[10][1<<15]={};
    dp[0][0]=1;
    for(int i=1; i<(1<<q); i++){
            for(int j=i; j>0; j=(j-1)&i){
                bool used[32]={};
                for(int p=0; p<q; p++){
                    if((i-j)&(1<<p)){
                        used[l[p]]=1, used[r[p]]=1;
                    }
                }
                bool dame=0;
                for(int p=0; p<q; p++){
                    if(j&(1<<p)){
                        if(used[l[p]] || used[r[p]]){
                            dame=1;
                            break;
                        }
                    }
                }
                if(dame) continue;
                for(int k=0; k<9; k++){
                    dp[k+1][i]+=(dp[k][i-j]*c[j]);
                    dp[k+1][i]%=MOD;
                }
            }
    }
    ll comb[9]={1, 8, 28, 56, 70, 56, 28, 8, 1};
    ll ans=0;
    for(int k=1; k<=9; k++){
      //cout<<dp[k][(1<<n)-1]*tot%MOD<<endl;
        ans+=dp[k][(1<<q)-1]*comb[k-1]%MOD*inv(k);
        ans%=MOD;
    }
    ans*=tot;
    ans%=MOD;
    cout<<ans<<endl;
    return 0;
}