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 <algorithm>
#include <cstdio>
using ll = long long;
constexpr int MOD = 1e9 + 7;
inline int quick_pow(int a, int n)
{
	int res = 1;
	while (n)
	{
		if (n & 1)
			res = (ll)res * a % MOD;
		a = (ll)a * a % MOD;
		n >>= 1;
	}
	return res;
}
int lp[35], rp[35], app[35], val[35], inv[35], dp[40005][15];
bool in_S[35], in_T[35];
int main()
{
	// freopen("B.in", "r", stdin);
	int n, q, cnt = 0, off = 0;
	scanf("%d%d", &n, &q);
	for (int i = 0; i < q; i++)
	{
		scanf("%d%d", lp + i, rp + i);
		app[cnt++] = --lp[i];
		app[cnt++] = rp[i];
	}
	std::sort(app, app + cnt);
	cnt = std::unique(app, app + cnt) - app;
	if (app[0])
	{
		off = app[0];
		n -= off;
		for (int i = 0; i < cnt; i++)
			app[i] -= off;
		for (int i = 0; i < q; i++)
		{
			lp[i] -= off;
			rp[i] -= off;
		}
	}
	for (int i = 0; i < q; i++)
	{
		lp[i] = std::lower_bound(app, app + cnt, lp[i]) - app;
		rp[i] = std::lower_bound(app, app + cnt, rp[i]) - app;
	}
	for (int i = 1; i < cnt; i++)
	{
		val[i] = (ll)(quick_pow(10, app[i] - app[i - 1]) - 1) * (MOD + 1) / 9 % MOD;
		inv[i] = quick_pow(val[i], MOD - 2);
	}
	auto get_in = [&] (int mask, bool * res)
	{
		for (int i = 0; i < cnt; i++)
			res[i] = false;
		for (int i = 0; i < q; i++)
		{
			if (mask & (1 << i))
				res[lp[i]] = res[rp[i]] = true;
		}
	};
	auto trans = [&] (int S, int T)
	{
		get_in(S, in_S);
		get_in(T, in_T);
		for (int i = 0; i < cnt; i++)
		{
			if (in_S[i] && in_T[i])
				return;
		}
		int coef = 1;
		for (int i = 1; i < cnt; i++)
		{
			if (in_T[i] && in_T[i - 1])
				coef = (ll)coef * (val[i] + 1) % MOD * inv[i] % MOD;
		}
		for (int i = 1; i < 10; i++)
			dp[S | T][i] = (dp[S | T][i] + (ll)dp[S][i - 1] * coef) % MOD;
	};
	dp[0][0] = 1;
	for (int i = 0; i + 1 < 1 << q; i++)
	{
		int rem = (1 << q) - 1 ^ i, low = rem & -rem;
		for (int j = rem ^ low; ; j = (j - 1) & (rem ^ low))
		{
			trans(i, j | low);
			if (!j)
				break;
		}
	}
	int ans = 0, cur = 1;
	for (int i = 1; i < 10; cur = cur * (9 - i), i++)
		ans = (ans + (ll)dp[(1 << q) - 1][i] * cur) % MOD;
	for (int i = 1; i < cnt; i++)
		ans = (ll)ans * val[i] % MOD;
	printf("%lld\n", (ll)ans * quick_pow(10, off + n - app[cnt - 1]) % MOD);
	return 0;
}