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 maxn 105
#define ll long long
#define ld double
#define mod 1000000007
using namespace std;
#define int long long
struct eg
{
	int u, v;
	ll a, b;
};
ll ksm(ll a, int b)
{
	if(!b) return 1;
	ll ns = ksm(a, b >> 1);
	ns = ns * ns % mod;
	if(b & 1) ns = ns * a % mod;
	return ns;
}
int d[maxn];
int tt[maxn];
int check(int a, int b, int c)
{
	if(a != b && a != c) return 1;
	return 0;
}
ll cal(int n, vector<eg> x)
{
	/*
	cout<<"CAL "<<n<<endl;
	for(int i = 0; i < x.size(); i++)
		cout<<x[i].u<<" "<<x[i].v<<" "<<x[i].a<<" "<<x[i].b<<endl;*/
		
	if(!n) return 1;
	int fl[20][20];
	memset(fl, 0, sizeof(fl));
	for(int j = 0; j < x.size(); j++)
	{
		if(fl[x[j].u][x[j].v]) while(1);
		if(x[j].u == x[j].v) while(1);
		fl[x[j].u][x[j].v] = 1, 
		fl[x[j].v][x[j].u] = 1;
	}
	d[0] = maxn;
	for(int i = 1; i <= n; i++)
		d[i] = 0;
	for(int j = 0; j < x.size(); j++)
		d[x[j].u]++, d[x[j].v]++;
//	if(n == 2) cout<<x[0].u<<" "<<x[]
	int mpl = 0;
	for(int i = 1; i <= n; i++)
		if(d[i] < d[mpl]) mpl = i;
	if(d[mpl] <= 1)
	{
		ll ans = 1;
		if(!d[mpl]) ans = 9;
		vector<eg> y;
		y.clear();
		for(int j = 0; j < x.size(); j++)
			if(x[j].u == mpl || x[j].v == mpl)
				ans = (8 * x[j].a + x[j].b) % mod;
			else
			{
				x[j].u -= (x[j].u >= mpl);
				x[j].v -= (x[j].v >= mpl);
				y.push_back(x[j]);
			}
	
		ll res = ans * cal(n - 1, y) % mod;
	/*	cout<<"CAL1 "<<n<<endl;
		for(int i = 0; i < x.size(); i++)
			cout<<x[i].u<<" "<<x[i].v<<" "<<x[i].a<<" "<<x[i].b<<endl;
		cout<<res<<endl;
	*/	return res;
	}	
//	cout<<"ASDD"<<n<<" "<<mpl<<" "<<d[mpl]<<endl;
//		for(int i = 0; i < x.size(); i++)
//		cout<<x[i].u<<" "<<x[i].v<<" "<<x[i].a<<" "<<x[i].b<<endl;
	for(int j = 0; j < x.size(); j++)
	{
		if(x[j].u != mpl && x[j].v != mpl) continue;
		ll ans = x[j].a;
		vector<eg> y;
		for(int i = 0; i < x.size(); i++)
			if(i != j) y.push_back(x[i]);
		ans = ans * cal(n, y) % mod;
		
		ll ans2 = x[j].b - x[j].a;
		int v = x[j].u + x[j].v - mpl;
		if(mpl > v) swap(v, mpl);
		y.clear();
		vector<ll> a, b;
		a.resize(n + 1), b.resize(n + 1);
		for(int i = 1; i <= n; i++)	
			a[i] = b[i] = 1;
		for(int i = 0; i < x.size(); i++)
		{
			int s = check(x[i].u, mpl, v) + check(x[i].v, mpl, v);
			if(s == 2)
			{
				x[i].u -= (x[i].u >= v), 
				x[i].v -= (x[i].v >= v);
			//	cout<<"PUSHx "<<x[i].u<<" "<<x[i].v<<" "<<v<<endl;
				y.push_back(x[i]);
			}
			else if(s == 1)
			{
				int nv = x[i].u;
				if(!check(x[i].u, mpl, v)) nv = x[i].v;
				a[nv] = a[nv] * x[i].a % mod, 
				b[nv] = b[nv] * x[i].b % mod;
			} 
		}
		for(int i = 1; i <= n; i++)
			if(a[i] != 1 || b[i] != 1)
			{
				eg n1;
				n1.u = mpl, n1.v = i - (i >= v);
			//	cout<<"PUSH"<<n1.u<<" "<<n1.v<<endl;
				n1.a = a[i], n1.b = b[i];
				y.push_back(n1); 
			}
		ans2 = ans2 * cal(n - 1, y) % mod;
		ans = (ans + ans2) % mod;
	//		cout<<"CAL2 "<<n<<endl;
	//	for(int i = 0; i < x.size(); i++)
	//		cout<<x[i].u<<" "<<x[i].v<<" "<<x[i].a<<" "<<x[i].b<<endl;
	//	cout<<ans<<endl;
		return ans;
	}
}
int n, q;
int fa[35];
int gfa(int a)
{
	if(fa[a] == a) return a;
	return fa[a] = gfa(fa[a]);
}
map<int, int> id;
int idcnt = 0;
int tr[35];
int u[35], v[35];
struct th
{
	int id, num;
	bool operator < (const th &l)const
	{
		return num < l.num;
	}
}s[35];
ll a[35][35], b[35][35];
ll bk9;
ll cala(int l)
{
	
	ll n1 = (ksm(10, l) - 1) * bk9 % mod;
	return n1;
}

ll calb(int l)
{
	return (cala(l) + 1) % mod;
}
#undef int
int main()
{
	#define int long long
	bk9 = ksm(9, mod - 2);
	id[0] = ++idcnt;
	cin>>n>>q;
	for(int i = 1; i <= q; i++)
	{
		cin>>u[i]>>v[i];
		u[i]--;
		if(!id[u[i]]) id[u[i]] = ++idcnt, tr[idcnt] = u[i];
		if(!id[v[i]]) id[v[i]] = ++idcnt, tr[idcnt] = v[i];
		u[i] = id[u[i]], v[i] = id[v[i]];
	}
	for(int i = 1; i <= idcnt; i++)
		fa[i] = i;
	for(int i = 1; i <= q; i++)
	{
		int ufa = gfa(u[i]), vfa = gfa(v[i]);
		fa[ufa] = vfa;
	}
	for(int i = 1; i <= idcnt; i++)
		s[i].id = i, s[i].num = tr[i];
	for(int i = 1; i <= idcnt; i++)
		for(int j = 1; j <= idcnt; j++)
			a[i][j] = b[i][j] = 1;
	sort(s + 1, s + idcnt + 1);
	ll ans = 1;
	for(int i = 1; i <= idcnt; i++)
	{
		if(i != 1)
		{
			int ufa = gfa(s[i - 1].id), vfa = gfa(s[i].id), l = s[i].num - s[i - 1].num;
			if(ufa == vfa) ans = ans * calb(l) % mod;//, cout<<l<<" "<<calb(l)<<endl;
			else
			{
				if(ufa > vfa) swap(ufa, vfa);
				a[ufa][vfa] = a[ufa][vfa] * cala(l) % mod;
				b[ufa][vfa] = b[ufa][vfa] * calb(l) % mod;
			//	cout<<"!!!"<<ufa<<" "<<vfa<<" "<<cala(l)<<" "<<calb(l)<<endl;
			}
		}
		if(i == idcnt)
			ans = ans * ksm(10, n - s[i].num) % mod;
		//	, cout<<n - s[i].num<<endl;
	}
	int s = 0;
	for(int i = 1; i <= idcnt; i++)
		if(gfa(i) == i)
			tt[i] = ++s;
//	cout<<ans<<endl;
	vector<eg> x;
	for(int i = 1; i <= idcnt; i++)
		for(int j = i + 1; j <= idcnt; j++)
			if(a[i][j] == 1 && b[i][j] == 1) continue;
			else
			{
				eg n1;
				n1.u = tt[i], n1.v = tt[j];
				n1.a = a[i][j], n1.b = b[i][j];
				x.push_back(n1);
			}
	ans = ans * cal(s, x) % mod;
	ans = ans * bk9 % mod;
	if(ans < 0) ans += mod;
	cout<<ans<<endl;
//	cout<<ans<<" "<<ksm(10, 184) * (ksm(2, 16) + 8) % mod<<endl;
	return 0;
}
/*
200
15
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16

 

*/