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;

const int M = 16;
const int MSK = 1 << 16;
const int mod = 1000000007;
const int inv9 = 111111112;

void add(int &x,int y) {
	x += y;
	if (x >= mod) {
		x -= mod;
	}
}

int mul(int x,int y) {
	return (long long) x * y % mod;
}

int power(int x,int y) {
	int ans = 1;
	while (y) {
		if (y & 1) {
			ans = mul(ans, x);
		}
		x = mul(x, x);
		y >>= 1;
	}
	return ans;
}

int val[M];
int f[MSK], nf[MSK], coef[MSK];
vector<pair<int, int>> go[M];

int main() {
	int n, m;
	scanf("%d %d", &n, &m);
	vector<pair<int, int>> all;
	
	all.push_back(make_pair(0, 0));
	
	for (int i = 1; i <= m; ++i) {
		int l, r;
		scanf("%d %d", &l, &r);
		--l;
		all.push_back(make_pair(l, i));
		all.push_back(make_pair(r, i));
	}
	++m;
	
	sort(all.begin(), all.end());
	
	int ans = 1;
	
	for (int i = 1; i < (int) all.size(); ++i) {
    	int u = all[i - 1].second, v = all[i].second;
    	if (all[i - 1].first == all[i].first) {
      	val[u] |= 1 << v;
      	val[v] |= 1 << u;
    	} else {
      	int nw = mul(inv9, power(10, all[i].first - all[i - 1].first) - 1);
      	ans = mul(ans, nw);
      	nw = mul(nw + 1, power(nw, mod - 2));
      	go[u].push_back(make_pair(v, nw));
    	}
  	}
  	ans = mul(ans, power(10, n - all.back().first));
	
	for (int msk = 0; msk < (1 << m); ++msk) {
    	coef[msk] = 1;
    	for (int i = 0; i < m; ++i) {
      	if (msk & (1 << i)) {
        		if ((val[i] & msk) != val[i]) {
          		coef[msk] = 0;
          		break;
        		}
        		for (auto p : go[i]) {
          		if (msk & (1 << p.first)) {
            		coef[msk] = mul(coef[msk], p.second);
          		}	
        		}
      	}
    	}
  	}
	
	f[0] = 1;
	for (int x = 0; x < 9; ++x) {
		for (int msk = 0; msk < (1 << m); ++msk) {
			int revmsk = msk ^ ((1 << m) - 1);
			for (int submsk = revmsk; ; submsk = (submsk - 1) & revmsk) {
				if (x || (submsk & 1)) {
					add(nf[msk | submsk], mul(f[msk], coef[submsk]));
				}
				if (!submsk) {
					break;
				}
			}
		}
		
		for (int msk = 0; msk < (1 << m); ++msk) {
			f[msk] = nf[msk];
			nf[msk] = 0;
		}
	}
	
	printf("%d\n", mul(ans, f[(1 << m) - 1]));
}