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 Mod = 1e9 + 7;
typedef long long ll;


void inm_to(int &a, int b) { a = (ll) a * b % Mod; }
int inm(int a, int b) { return (ll) a * b % Mod; }
void add_to(int &a, int b) { a += b; if(a >= Mod) a -= Mod; }

int power(int a, int b)
{
    int ans = 1;
    while(b)
    {
        if(b&1) inm_to(ans, a);
        inm_to(a, a); b >>= 1;
    }
    return ans;
}

int inv(int a)
{
    return power(a, Mod-2);
}

/////////////////////////////////////////////////////////

int N, M, cnt, pos[50], where[50], comp;
map<int,int> id;
pair<int,int> R[50];
int coef[1<<16], dp[1<<16], dp2[1<<16];


void dfs(int node, int comp)
{
    if(where[node]) return;

    where[node] = comp;
    int i;
    for(i=1; i<=M; ++i)
        if(R[i].first == pos[node])
            dfs(id[R[i].second], comp);

    for(i=1; i<=M; ++i)
        if(R[i].second == pos[node])
            dfs(id[R[i].first], comp);
}

void calc_subsets()
{
    int i, j, k;
    for(i=0; i<(1<<comp); ++i)
    {
        coef[i] = 1;

        for(j=0; j+1<cnt; ++j)
            if((i & (1<<where[j])) && (i & (1<<where[j+1])))
                inm_to(coef[i], 1 + inm(9, inv(power(10, pos[j+1] - pos[j]) - 1)));
    }
}

void do_dp()
{
    int i, j;
    for(i=0; i<(1<<comp); ++i)
    {
        for(j=i; j; j = (j-1) & i)
            add_to(dp2[i], inm(dp[j], coef[i ^ j]));
        add_to(dp2[i], inm(dp[0], coef[i]));
    }
}

void solve()
{
    int i, j;
    dp[0] = 1;

    for(i=0; i<9; ++i)
    {
        do_dp();
        for(j=0; j<(1<<comp); ++j)
            dp[j] = dp2[j], dp2[j] = 0;
    }

    int ans = dp[(1<<comp) - 1];

    inm_to(ans, power(10, pos[0]));
    inm_to(ans, power(10, N - pos[cnt - 1]));

    for(i=0; i+1 < cnt; ++i)
        inm_to(ans, inm( power(10, pos[i+1] - pos[i]) - 1, inv(9) ));
    cout << inm(ans, inv(9)) << '\n';
}

int main()
{
  //  freopen("input", "r", stdin);
    cin.sync_with_stdio(false);

    cin >> N >> M;

    int i, x, y;
    for(i=1; i<=M; ++i)
    {
        cin >> x >> y; --x;
        R[i] = {x, y};
        id[x] = 1; id[y] = 1;
    }

    cnt = 0;
    for(auto &it : id)
    {
        it.second = cnt;
        pos[cnt] = it.first;
        cnt++;
    }

    comp = 0;
    for(i=0; i<cnt; ++i)
        if(!where[i])
        {
            ++comp;
            dfs(i, comp);
        }

    for(i=0; i<cnt; ++i) where[i] --;

    calc_subsets();
    solve();

    return 0;
}