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 LL long long
#define uLL unsigned long long
#define db double

using namespace std;
const int N=16,M=(1<<15)+10,mod=1e9+7,inv9=111111112;
int rd()
{
    int x=0,w=1;char ch=0;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*w;
}
void ad(int &x,int y){x+=y,x-=x>=mod?mod:0;}
int fpow(int a,int b){int an=1;while(b){if(b&1) an=1ll*an*a%mod;a=1ll*a*a%mod,b>>=1;} return an;}
int n,m,a[N][3],b[N<<1],sd[N<<1],t,l2[M],f[2][M],g[M],h[M],st[M],tp;

int main()
{
	n=rd(),m=rd();
	for(int i=1;i<=m;++i) b[2*i-1]=a[i][0]=rd()-1,b[2*i]=a[i][1]=rd(),a[i][2]=0;
	bool fg=1;
	t=2*m;
	for(int i=1;i<=t;i+=2) if(!b[i]){fg=0;break;}
	if(fg) ++t;
	sort(b+1,b+t+1),t=unique(b+1,b+t+1)-b-1;
	for(int i=1;i<=t;++i) sd[i]=fpow(10,b[i]-b[i-1]);
	for(int i=1;i<=m;++i)
		for(int j=0;j<=2;++j)
			a[i][j]=lower_bound(b+1,b+t+1,a[i][j])-b;
	int u=(1<<m)-1;
	for(int i=1;i<=u;++i) l2[i]=l2[i>>1]+1;
	int nw=1,la=0;
	f[la][0]=1;g[0]=1;
	for(int z=0;z<9;++z)
	{
		for(int i=0;i<=u;++i)
		{
			if(!f[la][i]) continue;
			ad(f[nw][i],f[la][i]);
			tp=0;
			for(int j=u^i;j;j=(j-1)&(u^i)) st[++tp]=j;
			h[0]=(bool)z;
			for(int j=1;j<=m;++j)
				if(i>>(j-1)&1) h[0]|=(1<<(a[j][0]-1))|(1<<(a[j][1]-1));
			for(int jj=tp;jj;--jj)
			{
				int j=st[jj];
				int lj=j^(j&(-j)),k=l2[j&(-j)];
				if((h[0]>>(a[k][0]-1)&1)||(h[0]>>(a[k][1]-1)&1)) continue;
				h[j]=h[lj],g[j]=g[lj];
				for(int o=0;o<=1+(!z);++o)
				{
					int x=a[k][o];
					if(h[j]>>(x-1)&1) continue;
					if(x>1&&h[j]>>(x-2)&1)
						g[j]=1ll*g[j]*(1ll*(sd[x]-1)*inv9%mod+(!(h[0]>>(x-2)&1)))%mod;
					if(h[j]>>x&1)
						g[j]=1ll*g[j]*(1ll*(sd[x+1]-1)*inv9%mod+(!(h[0]>>x&1)))%mod;
					h[j]|=1<<(x-1);
				}
				ad(f[nw][i|j],1ll*f[la][i]*g[j]%mod);
			}
			while(tp) g[st[tp]]=h[st[tp]]=0,--tp;
			f[la][i]=0;
		}
		nw^=1,la^=1;
	}
	int ans=1ll*f[la][u]*fpow(10,n-b[t])%mod;
	printf("%d\n",ans);
    return 0;
}