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>
using namespace std;
#define rep(i,a,b) for(int i = (a); i < (b); ++i)
#define rrep(i,a,b) for(int i = (b); i --> (a);)
#define trav(x,v) for(auto  &x : v)
#define all(v) (v).begin(),(v).end()
#define sz(v) (int)(v).size()
typedef pair<int,int> pii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;

const ll md = 1e9+7;

ll mpow(ll a, int e){
	ll res = 1;
	do {
		if(e & 1) res = res * a % md;
		a = a * a % md;
	} while(e >>= 1);
	return res;
}

ll ninv = mpow(9, md-2);

ll fun(int len){
	return (mpow(10,len)-1)*ninv % md;
}

int main(){
	cin.sync_with_stdio(0); cin.tie(0);
	cin.exceptions(cin.failbit);

	int n, q;
	cin >> n >> q;

	vector<pii> lr(q);
	trav(pa, lr) cin >> pa.first >> pa.second, --pa.first;
	
	map<int,int> ren;
	trav(pa, lr) ren[pa.first] = ren[pa.second] = 0;
	int ix = 0;
	trav(pa, ren) pa.second = ix++;
	vi ner(ix);
	trav(pa, ren) ner[pa.second] = pa.first;

	auto uni = [&](vi &cmp, int a, int b){
		a = cmp[a], b = cmp[b];
		if(a == b) return;
		if(b < a) swap(a,b);
		trav(x, cmp) if(x == a) x = b;
	};

	vi cmp(ix);
	rep(i,0,ix) cmp[i] = i;
	trav(pa, lr) uni(cmp, ren[pa.first], ren[pa.second]);

	int nix = 0;
	vi num(ix,-1);
	rep(i,0,ix) if(cmp[i] == i) num[i] = nix++;

	map<pair<int,ll>,ll> mem;

	function<ll(int,vi)> rek = [&](int l, vi cmp){
		if(l == ix-1) return 1LL;

		ll hs = 0;
		rep(i,0,ix) if(num[i] >= 0) hs = (hs<<4) | num[cmp[i]];
		pair<int,ll> hsh(l, hs);

		if(!mem.count(hsh)){
			ll ans;
			int len = ner[l+1] - ner[l];
			if(cmp[l] == l){
				ans = rek(l+1,cmp)*mpow(10,len) % md;
			} else if(cmp[l] == cmp[l+1]) {
				ans = rek(l+1,cmp)*(1 + fun(len)) % md;
			} else {
				ans = rek(l+1,cmp)*fun(len) % md;
				uni(cmp, l, l+1);
				ans = (ans + rek(l+1,cmp)) % md;
			}
			return mem[hsh] = ans;
		}
		return mem[hsh];
	};
	cout << mpow(10, ner[0] + n-ner[ix-1]) * rek(0, cmp)%md << endl;
}