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<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
using namespace std;

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = mod * mod;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef pair<ll, ll> LP;
typedef vector<ll> vec;
typedef vector<string> svec;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-8;

vector<int> ch[1 << 15];
void init() {
	rep(i, (1 << 15)) {
		vector<int> v;
		rep(j, 15) {
			if (i&(1 << j)) {
				v.push_back(j);
			}
		}
		int len = v.size();
		rep(j, (1 << len)) {
			int s = 0;
			rep(k, len) {
				if (j&(1 << k)) {
					s += (1 << v[k]);
				}
			}
			ch[i].push_back(s);
		}
	}
}
ll mod_pow(ll x, int n) {
	ll ret = 1;
	while (n > 0) {
		if (n % 2)ret = ret * x%mod;
		x = x * x%mod; n >>= 1;
	}
	return ret;
}

int loc[15][2];
bool same[15][15];

bool valid[1 << 15];
ll num[1 << 15];
ll num0[1 << 15];

ll dp[1 << 15];

void solve() {
	int n, q; cin >> n >> q;
	vector<P> v(q);
	vector<int> x;
	rep(i, q) {
		cin >> v[i].first >> v[i].second; v[i].first--;
		x.push_back(v[i].first);
		x.push_back(v[i].second);
	}
	sort(x.begin(), x.end());
	x.erase(unique(x.begin(), x.end()),x.end());
	map<int, int> mp;
	rep(i, x.size())mp[x[i]] = i;
	rep(i, q) {
		loc[i][0] = mp[v[i].first];
		loc[i][1] = mp[v[i].second];
	}
	rep(i, q) {
		Rep(j, i + 1, q) {
			rep(k, 2) {
				rep(l, 2) {
					if (loc[i][k] == loc[j][l]) {
						same[i][j] = true;
					}
				}
			}
		}
	}
	fill(valid, valid + (1 << q), true);
	rep(i, (1 << q)) {
		bool isi[15] = {};
		rep(j, q) {
			if (i&(1 << j)) {
				isi[j] = true;
			}
		}
		rep(j, q) {
			Rep(k, j + 1, q) {
				if (same[j][k]) {
					if (isi[j] != isi[k]) {
						valid[i] = false;
					}
				}
			}
		}
	}
	rep(i, (1 << q)) {
		if (!valid[i])continue;
		vector<int> loc;
		rep(j, q) {
			if (i&(1 << j)) {
				loc.push_back(mp[v[j].first]);
				loc.push_back(mp[v[j].second]);
			}
		}
		sort(loc.begin(), loc.end());
		loc.erase(unique(loc.begin(), loc.end()),loc.end());
		num[i] = 1;
		num0[i] = 1;
		rep(j, loc.size()) {
			int dif = x[loc[j]];
			if (loc[j] > 0) {
				dif -= x[loc[j] - 1];
			}
			ll c = mod_pow(10, dif); c--;
			if (c < 0)c += mod;
			c = c * (mod + 1) / 9 % mod;
			//same:no
			if (j > 0 && loc[j] == loc[j - 1]+1) {
				num[i] = num[i] * (c + 1) % mod;
				num0[i] = num0[i] * (c + 1) % mod;
			}
			else {
				if (loc[j] == 0) {
					num0[i] = num0[i] * (c + 1) % mod;
				}
				else {
					num0[i] = num0[i] * c%mod;
				}
				if (x[loc[j]] == 0) {
					num[i] = 0;
				}
				else {
					num[i] = num[i] * c%mod;
				}
			}
		}
	}
	dp[0] = 1;
	for (int i = (1 << q) - 1; i >= 0; i--) {
		int xi = ((1 << q) - 1) ^ i;
		rep(j, ch[xi].size()) {
			int s = ch[xi][j];
			if (s == 0)continue;
			if (!valid[s])continue;
			dp[i^s] = (dp[i^s] + dp[i] * num0[s]) % mod;
		}
	}
	rep(aa, 8) {
		for (int i = (1 << q) - 1; i >= 0; i--) {
			int xi = ((1 << q) - 1) ^ i;
			rep(j, ch[xi].size()) {
				int s = ch[xi][j];
				if (s == 0)continue;
				if (!valid[s])continue;
				dp[i^s] = (dp[i^s] + dp[i] * num[s]) % mod;
			}
		}
	}
	ll ans = dp[(1 << q) - 1];
	int ma = 0;
	rep(i, q) {
		ma = max(ma, v[i].second);
	}
	int dif = n - ma;
	ans = ans * mod_pow(10, dif) % mod;
	cout << ans << endl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(10);
	init();
	solve();
	//cout << "finish" << endl;
	//stop
	return 0;
}