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 <map>
#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define set0(x) memset(x,0,sizeof(x))
#define FF first
#define SS second
#define PB push_back
#define MP make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
template<typename T> void read(T &x){
	x = 0;char ch = getchar();int f = 1;
	while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
	while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
int mod = 1000000007;
inline int sq(int x){return 1ll*x*x%mod;}
inline int sub(int a,int b){return a<b?a-b+mod:a-b;}
inline int add(int a,int b){return a+b>=mod?a+b-mod:a+b;}
inline int mul(int a,int b){return 1ll*a*b%mod;}
inline int pow(int a,int b){if(b == 0)return 1;return b&1?mul(sq(pow(a,b/2)),a):sq(pow(a,b/2));}
inline int inv(int a){return pow(a,mod-2);}
int n,q,l[20],r[20],conn[20][20],bcj[20],isp,oriv[33000],pool[10][33000] = {0};
vector<pii> poi;
int fnd(int x){
	return bcj[x] == x?x:bcj[x] = fnd(bcj[x]);
}
int main() {
	read(n);
	read(q);
	int tp = -1;
	for(int i=0;i<q;i++){
		read(l[i]);read(r[i]);
		poi.push_back(MP(l[i]-1,i));
		poi.push_back(MP(r[i],i));
		//cout<<l[i]-1<<' '<<r[i]<<endl;
	}
	for(int i=0;i<q;i++)bcj[i] = i;
	for(int i=0;i<q;i++)for(int j=0;j<q;j++)conn[i][j] = 1;
	sort(poi.begin(),poi.end());
	int cq = 0;
	for(int i=0;i<poi.size()-1;i++){
		while(i<poi.size()-1 && poi[i].FF == poi[i+1].FF){
			if(fnd(poi[i].SS)!=fnd(poi[i+1].SS))bcj[fnd(poi[i].SS)] = fnd(poi[i+1].SS);
			poi.erase(poi.begin()+i);
		}
	}
	
	int ccnt[20] = {0};
	for(int i=0;i<=q;i++)ccnt[fnd(i)]=1;
	for(int i=1;i<=q;i++)ccnt[i]+=ccnt[i-1];
	for(int i=0;i<poi.size();i++)poi[i].SS = ccnt[fnd(poi[i].SS)]-1;
	int m = ccnt[q],cans = 1,inv9 = inv(9);
	if(poi[0].FF!=0)cans = mul(sub(pow(10,poi[0].FF),1),inv9);
	int cf = mul(sub(pow(10,poi[0].FF),1),inv9);
	for(int i=0;i<poi.size();i++){
		//cout<<poi[i].FF<<' '<<poi[i].SS<<endl;
		if(poi[i].FF == 0)isp|=1<<poi[i].SS;
		for(int j=i+1;j<poi.size();j++){
			if(poi[j].FF!=poi[i].FF){
				if(isp&(1<<poi[i].SS) && poi[j].FF==poi[i].FF)isp|=1<<poi[j].SS;
				int cd = mul(sub(pow(10,poi[j].FF-poi[i].FF),1),inv9),cc = mul(add(cd,1),inv(cd));
				cans = mul(cans,cd);
				if(poi[i].SS!=poi[j].SS){
					conn[poi[i].SS][poi[j].SS] = mul(conn[poi[i].SS][poi[j].SS],cc);
					conn[poi[j].SS][poi[i].SS] = mul(conn[poi[j].SS][poi[i].SS],cc);
				}else{
					cans = mul(cans,cc);
				}
				break;
			}
		}
	}
	cans = mul(pow(10,n-poi[poi.size()-1].FF),cans);
	//cout<<cans<<' '<<cf<<endl;
	oriv[0] = 1;
	for(int i=0;i<1<<m;i++){
		if(i){
			int lo = __builtin_ctz(i);
			oriv[i] = oriv[i-(1<<lo)];
			for(int j = lo;1<<j<=i;j++) if((1<<j)&i)oriv[i] = mul(oriv[i],conn[lo][j]);
		}
		if((i&isp) == isp){
			pool[0][i] = mul(cans,oriv[i]);
			if(i>>poi[0].SS&1 && poi[0].FF)pool[0][i] = mul(pool[0][i],mul(cf+1,inv(cf)));
			//cout<<i<<' '<<pool[0][i]<<endl;
		}
	}
	for(int i=1;i<9;i++){
		for(int j=0;j<1<<m;j++){
			int cc = 0;
			for(int k=j;;k = (k-1)&j){
				cc = add(cc,mul(pool[i-1][k],oriv[k^j]));
				if(k == 0)break;
			}
			pool[i][j] = cc;
		}
	}
	cout<<pool[8][(1<<m)-1]<<endl;
	return 0;
}