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;

using ll = long long;

const int MOD = 1e9 + 7;

int powmod(int a, int b) {
	int r = 1;
	while (b) {
		if (b & 1) {
			r = ll(r) * a % MOD;
		}
		a = ll(a) * a % MOD;
		b /= 2;
	}
	return r;
}

const int MAXQ = 16;
int N, Q;
int adj[MAXQ];

vector<pair<int, int>> extra[MAXQ];
int coeff[1 << MAXQ];
int dp[2][1 << MAXQ];

const int i9 = powmod(9, MOD - 2);

int main() {
	vector<pair<int, int>> pts = {{0, 0}};
	scanf("%d %d", &N, &Q); Q++;
	for (int i = 1; i < Q; i++) {
		int l, r; scanf("%d %d", &l, &r); l--;
		pts.emplace_back(l, i);
		pts.emplace_back(r, i);
	}

	sort(pts.begin(), pts.end());
	int ans = powmod(10, N - pts.back().first);

	for (size_t i = 0; i + 1 < pts.size(); i++) {
		int x = pts[i].second;
		int y = pts[i + 1].second;
		if (pts[i].first == pts[i + 1].first) {
			adj[x] |= 1 << y;
			adj[y] |= 1 << x;
		} else {
			int base = ll(i9) * (powmod(10, pts[i + 1].first - pts[i].first) - 1) % MOD;
			ans = ll(ans) * base % MOD;
			base = ll(base + 1) * powmod(base, MOD - 2) % MOD;
			extra[x].emplace_back(y, base);
		}
	}

	for (int m = 0; m < (1 << Q); m++) {
		coeff[m] = 1;
		for (int i = 0; i < Q; i++) {
			if (!(m & (1 << i))) continue;
			if ((adj[i] & m) != adj[i]) {
				coeff[m] = 0;
				break;
			}
			for (auto p : extra[i]) {
				if (m & (1 << p.first)) {
					coeff[m] = ll(p.second) * coeff[m] % MOD;
				}
			}
		}
	}

	int cur = 0, nxt = 1;
	dp[0][0] = 1;
	for (int x = 0; x < 9; x++, swap(cur, nxt)) {
		memset(dp[nxt], 0, sizeof(int) * (1 << Q));
		
		for (int m = 0; m < (1 << Q); m++) {
			int cm = (1 << Q) - 1 - m;
			for (int s = cm; ; s = (s - 1) & cm) {
				if ((s & 1) || x) {
					dp[nxt][s | m] += ll(dp[cur][m]) * coeff[s] % MOD;
					if (dp[nxt][s | m] >= MOD) {
						dp[nxt][s | m] -= MOD;
					}
				}
				if (s == 0) break;
			}
		}
	}
	ans = ll(ans) * dp[cur][(1 << Q) - 1] % MOD;

	printf("%d\n", ans);

	return 0;
}