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<iostream>
#include<cstdio>
#include<map>
#include<algorithm>
#define maxn 20
#define ll long long
#define mod 1000000007
using namespace std;
int n,m,q,x,y,cnt=0,tim=0;
int node[maxn<<1],lid[maxn<<1],rid[maxn<<1];
ll ans,val[maxn<<1],dlt[1<<maxn],f[10][1<<maxn];
map<int,int>fa,id;
int find(int x){
	return fa.count(x)?fa[x]=find(fa[x]):x;
}
ll ksm(ll x,ll i){
	ll res=1;
	for(;i;i>>=1,x=x*x%mod)
		if(i&1)res=res*x%mod;
	return res;
}
int main(){
	scanf("%d%d",&n,&q);
	for(register int i=1;i<=q;i++){
		scanf("%d%d",&x,&y);
		if(x>y)swap(x,y);
		x--;
		node[++cnt]=x;
		node[++cnt]=y;
		int fx=find(x),fy=find(y);
		if(fx>fy)swap(fx,fy);
		if(fx!=fy)fa[fy]=fx;
	}
	node[++cnt]=0;
	sort(node+1,node+cnt+1);
	cnt=unique(node+1,node+cnt+1)-node-1;
	ans=1;
	for(register int i=1,lst=0;i<=cnt;lst=node[i],i++){
		int now=node[i];
		id[now]=fa.count(now)?id[find(now)]:tim++;
		lid[i]=id[lst];
		rid[i]=id[now];
		if(!now){
			ans=ans*ksm(9,mod-2)%mod;
			val[i]=1;
		}
		else{
			ll res=(ksm(10,now-lst)-1)*ksm(9,mod-2)%mod;
			//cout<<"res="<<res<<endl;
			ans=ans*res%mod;
			val[i]=(res+1)*ksm(res,mod-2)%mod;
		}
		//cout<<i<<" lid="<<lid[i]<<" rid="<<rid[i]<<" val="<<val[i]<<endl;
	}
	//cout<<"tim="<<tim<<endl;
	if(node[cnt]<n)ans=ans*ksm(10,n-node[cnt])%mod;
	m=(1<<tim);
	for(register int i=0;i<m;i++){
		dlt[i]=1;
		for(register int j=2;j<=cnt;j++){
			//cout<<i<<" l="<<lid[j]<<" r="<<rid[j]<<endl;
			if(((i>>lid[j])&1)&&((i>>rid[j])&1))dlt[i]=dlt[i]*val[j]%mod;
		}
		f[0][i]=dlt[i];
	}
	for(register int i=0;i<8;i++){
		for(register int j=0;j<m;j++){
			for(register int k=j;k<m;k=(k+1)|j){
				f[i+1][k]=(f[i+1][k]+f[i][j]*dlt[j^k]%mod)%mod;
			}
		}
	}
	/*for(register int i=0;i<9;i++){
		for(register int j=0;j<m;j++){
			cout<<"f["<<i<<"]["<<j<<"]="<<f[i][j]<<endl;
		}
	}
	cout<<ans<<" "<<f[8][m-1]<<endl;*/
	printf("%lld",ans*f[8][m-1]%mod);
	return 0;
}