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;

typedef pair<int, int> pii;
typedef long long ll;
template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()
#define dump(x) cerr << #x << " = " << (x) << endl
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

template<class T, class U> void chmin(T& t, const U& u) { if (t > u) t = u; }
template<class T, class U> void chmax(T& t, const U& u) { if (t < u) t = u; }

template<class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	os<<"{";
	rep(i, v.size()) {
		if (i) os<<",";
		os<<v[i];
	}
	os<<"}";
	return os;
}

template <unsigned int MOD>
struct ModInt {
	using uint = unsigned int;
	using ull = unsigned long long;
	using M = ModInt;

	uint v;

	ModInt(ll _v = 0) { set_norm(_v % MOD + MOD); }
	M& set_norm(uint _v) { //[0, MOD * 2)->[0, MOD)
		v = (_v < MOD) ? _v : _v - MOD;
		return *this;
	}

	explicit operator bool() const { return v != 0; }
	M operator+(const M& a) const { return M().set_norm(v + a.v); }
	M operator-(const M& a) const { return M().set_norm(v + MOD - a.v); }
	M operator*(const M& a) const { return M().set_norm(ull(v) * a.v % MOD); }
	M operator/(const M& a) const { return *this * a.inv(); }
	M& operator+=(const M& a) { return *this = *this + a; }
	M& operator-=(const M& a) { return *this = *this - a; }
	M& operator*=(const M& a) { return *this = *this * a; }
	M& operator/=(const M& a) { return *this = *this / a; }
	M operator-() const { return M() - *this; }
	M& operator++(int) { return *this = *this + 1; }
	M& operator--(int) { return *this = *this - 1; }

	M pow(ll n) const {
		if (n < 0) return inv().pow(-n);
		M x = *this, res = 1;
		while (n) {
			if (n & 1) res *= x;
			x *= x;
			n >>= 1;
		}
		return res;
	}

	M inv() const {
		ll a = v, b = MOD, p = 1, q = 0, t;
		while (b != 0) {
			t = a / b;
			swap(a -= t * b, b);
			swap(p -= t * q, q);
		}
		return M(p);
	}

	bool operator==(const M& a) const { return v == a.v; }
	bool operator!=(const M& a) const { return v != a.v; }
	friend ostream& operator<<(ostream& os, const M& a) { return os << a.v; }
};

using Mint = ModInt<1000000007>;

class unionfind {
	vector<int> par, rank;

public:
	void init(int n) {
		par.resize(n);
		rank.resize(n);

		for (int i = 0; i < n; i++) {
			par[i] = i;
			rank[i] = 0;
		}
	}

	int find(int x) {
		if (par[x] == x) return x;
		else return par[x] = find(par[x]);
	}

	void unite(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y) return ;

		if (rank[x] < rank[y]) par[x] = y;
		else {
			par[y] = x;
			if (rank[x] == rank[y]) ++rank[x];
		}
	}

	bool same(int x, int y) { return (find(x) == find(y)); }
} uf;

Mint dp[11][1<<15];

int main() {
	int N, Q; cin >> N >> Q;

	V<int> xs;
	V<pii> qr;

	rep(i, Q) {
		int l, r;
		cin >> l >> r;
		--l;
		qr.eb(l, r);
		xs.pb(l);
		xs.pb(r);
	}
	sort(ALL(xs));
	xs.erase(unique(ALL(xs)), xs.end());

	uf.init(xs.size());

	rep(i, Q) {
		int p, q;
		tie(p, q) = qr[i];
		p = lower_bound(ALL(xs), p) - xs.begin();
		q = lower_bound(ALL(xs), q) - xs.begin();
		uf.unite(p, q);
		qr[i] = mp(p, q);
	}

	VV<int> _vpos(Q * 2);
	rep(i, Q) {
		int p, q;
		tie(p, q) = qr[i];
		int id = uf.find(p);
		_vpos[id].pb(p); _vpos[id].pb(q);
	}

	VV<int> vpos;
	rep(i, Q * 2) if (_vpos[i].size() > 0) {
		sort(ALL(_vpos[i]));
		_vpos[i].erase(unique(ALL(_vpos[i])), _vpos[i].end());
		vpos.eb(_vpos[i]);
	}
	Q = vpos.size();

	V<Mint> coef(1 << Q);
	V<int> zero(1 << Q);

	rep(i, 1 << Q) { //these values are same
		Mint v(1);
		V<int> pos;
		rep(j, Q) if ((i >> j) & 1) {
			for (int x : vpos[j]) {
				pos.pb(x);
			}
		}
		sort(ALL(pos));
		if (pos.size() && pos[0] == 0) {
			zero[i] = 1;
		}

		rep(j, (int)pos.size() - 1) {
			if (pos[j+1] == pos[j] + 1) {
				auto cur = (Mint(10).pow(xs[pos[j+1]] - xs[pos[j]]) - Mint(1)) / Mint(9);
				v = v * (cur + Mint(1)) / cur;
			}
		}
		coef[i] = v;
	}

	{
		Mint all = Mint(10).pow(xs[0] + N - xs.back()); //consider pref[xs[0]] as zero
		rep(i, xs.size()) {
			if (i) {
				all *= (Mint(10).pow(xs[i] - xs[i-1]) - Mint(1)) / Mint(9);
			}
		}
		rep(i, 1 << Q) if (zero[i]) {
			dp[0][i] = all * coef[i];
		}
	}

	rep(d, 8) {
		rep(i, 1 << Q) {
			for (int j = i; ; j = (j-1) & i) {
				if (dp[d][i^j]) {
					dp[d+1][i] += dp[d][i^j] * coef[j];
				}
				if (j == 0) break;
			}
		}
	}

	cout << dp[8][(1<<Q)-1] << endl;

	return 0;
}