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<bits/stdc++.h>
#define Q 22
#define ll long long
#define mo 1000000007
#define ni9 111111112
using namespace std;
template <typename T> void read(T &x){
	x=0;char c=getchar();int fh=1;
	while (!isdigit(c)){if (c=='-')fh=-1;c=getchar();}
	while (isdigit(c))x=x*10+c-'0',c=getchar();
	x*=fh;
}
struct Info{int nu,we,nn;}a[Q*2];
int n,q,f[Q*2],bi[Q*2],su[Q],ns,g[Q*2],m;
ll dp[33010][2],an[Q*2];
vector<int> zh[33010],z1[33010];
bool comp(const Info &a,const Info &b){return a.nu<b.nu;}
bool comp1(const Info &a,const Info &b){return a.we<b.we;}
int que(int x){if (f[x]!=x)f[x]=que(f[x]);return f[x];}
void he(int x,int y){int nx=que(x),ny=que(y);if(nx!=ny)f[nx]=ny;}
ll po(ll x,ll y){ll z=1;while (y){if (y%2)z=x*z%mo;x=x*x%mo;y/=2;}return z;}
ll qu(int x,int y){
	int p=0,q=0;ll ans=1;
	for (int i=1;i<=ns;i++)
		if ((x&(1<<(i-1)))!=0)p+=su[i];else if ((y&(1<<(i-1)))!=0)q+=su[i];
	for (int i=1;i<m;i++){
		if ((q&(1<<(i-1)))!=0&&(q&(1<<i))!=0)ans=ans*(an[i]+1)%mo;
		if ((q&(1<<(i-1)))!=0&&(p&(1<<i))!=0)ans=ans*an[i]%mo;
		if ((p&(1<<(i-1)))!=0&&(q&(1<<i))!=0)ans=ans*an[i]%mo;
	}
	return ans;
}
ll qu1(int x,int y){
	int p=0,q=0;ll ans=1;
	for (int i=1;i<=ns;i++)
		if ((x&(1<<(i-1)))!=0)p+=su[i];else if ((y&(1<<(i-1)))!=0)q+=su[i];
	for (int i=1;i<m;i++){
		if ((q&(1<<(i-1)))!=0&&(q&(1<<i))!=0)ans=ans*(an[i]+1)%mo;
		if ((q&(1<<(i-1)))!=0&&(p&(1<<i))!=0)ans=ans*an[i]%mo;
		if ((p&(1<<(i-1)))!=0&&(q&(1<<i))!=0)ans=ans*an[i]%mo;
	}
	if (q%2==1) ans=ans*(an[0]+1)%mo;else ans=ans*an[0]%mo;
	return ans;
}
int main(){
	read(n);read(q);
	for (int i=1;i<=q;i++){read(a[i].nu);a[i].nu--;read(a[i+q].nu);}
	for (int i=1;i<=q+q;i++)a[i].we=i;
	sort(a+1,a+q+q+1,comp);
	for (int i=1;i<=q+q;i++){
		a[i].nn=a[i-1].nn+(i==1||a[i].nu!=a[i-1].nu);
		g[a[i].nn]=a[i].nu;
	}
	m=a[q+q].nn;
	sort(a+1,a+q+q+1,comp1);
	for (int i=1;i<=m;i++) f[i]=i;
	for (int i=1;i<=q;i++)he(a[i].nn,a[i+q].nn);
	for (int i=1;i<=m;i++) if (f[i]==i) bi[i]=++ns;
	for (int i=1;i<=m;i++){
		int no=bi[que(i)];
		su[no]+=(1<<(i-1));
	}
	for (int i=0;i<m;i++)an[i]=(po(10,g[i+1]-g[i])+mo-1)*ni9%mo;
	for (int i=0;i<(1<<ns);i++)zh[0].push_back(i);
	for (int i=1;i<(1<<ns);i++)
		for (int j=0;j<zh[i/2].size();j++)
			if ((zh[i/2][j]&(1<<(ns-1)))==0){
				zh[i].push_back(zh[i/2][j]*2+1);
				if (i%2==0) zh[i].push_back(zh[i/2][j]*2);
			}
	for (int i=0;i<(1<<ns);i++)
		for (int j=0;j<zh[i].size();j++)z1[i].push_back(qu(i,zh[i][j]));
	if (g[1]==0&&m>=1){
		int nu=0;
		for (int i=1;i<=ns;i++) if (su[i]%2==1) nu=i;
		for (int i=0;i<(1<<ns);i++)if ((i&(1<<nu-1))!=0)dp[i][0]=qu(0,i);
	}else{
		for (int i=0;i<(1<<ns);i++) dp[i][0]=qu1(0,i);
	}
	for (int ne=1;ne<=8;ne++){
		for (int j=0;j<(1<<ns);j++)
			if (dp[j][0])
				for (int i=0;i<zh[j].size();i++)
					dp[zh[j][i]][1]=(dp[zh[j][i]][1]+dp[j][0]*z1[j][i])%mo;
		for (int j=0;j<(1<<ns);j++){dp[j][0]=dp[j][1];dp[j][1]=0;}
	}
	ll ans=dp[(1<<ns)-1][0];
	cout<<ans*po(10,n-g[m])%mo<<endl;
	return 0;
}
/*
30 10
1 1
3 3
5 5
7 7
9 9
11 11
13 13
15 15
17 17
19 19
*/