GridPath

#include <bits/stdc++.h>

#include"map"
#include"set"
#include"queue"
#include"cmath"
#include"stack"
#include"ctype.h"
#include"cstdio"
#include"vector"
#include"cstdio"
#include"cstring"
#include"cstdlib"
#include"string.h"
#include"iostream"
#include"algorithm"
using namespace std;
#define cs "Case "<<++casee<<": "
#define csE "Case "<<++casee<<":\n"
#define sf(t) scanf("%d",&t)
#define sNE(n,e) scanf("%d %d",&N,&E)
#define Inf 1000000000
#define S_N 5000010
#define size_N 10000000
#define MST(a, tf) memset(a, tf, sizeof (a))

using namespace std;

/*
Algorithm:

1. Calculate the total number of paths on a (n x n) grid considering there's no trap.
2. Calculate the total number of paths that generate from (1,1) block to the trap block. (Al of these paths are invalid)
3. Calculate the total number of paths that generate from the trap block to the destination block, that is, bottom right corner (Al off these paths are invalid)
4. Note: If a trap falls within the area of another trap, we will subtract the overlapping paths to avoid double-counting!
5. Now subtract these invalid paths from total paths to get the final answer.
*/

typedef long long ll;

ll M = 1000000007; // 1000000007 [M is a prime number]
const ll N = 2000005;

ll factorial[N];

struct Trap
{
    ll y, x;
};

// custom sorting implementation
bool compareTrap(Trap trap1, Trap trap2)
{
    // if y values are different, sort by minimum y values
    if(trap1.y != trap2.y)
        return trap1.y < trap2.y;

    // otherwise, sort by minimum x values
    return trap1.x < trap2.x;
}

vector<Trap> trapIndex;

// This function calculates (a^b) % M
ll power(ll a, ll b)
{
    ll x = 1;
    ll y = a;

    while (b > 0)
    {
        if (b % 2)
        {
            x = (x * y) % M;
        }
        y = (y * y) % M;
        b /= 2;
    }

    return x % M;
}

ll modular_inverse(ll n)
{
    return power(n, M-2);
}

/*
Algorithm for efficient nCr calculation:

1. Let’s say we I want to find 5C2
2. We don’t need inverse of 3 and 2
3. Instead we need the inverse of 3! = 6 and 2! = 2
4. Because nCr is equal to n! / ( r! * (n — r)! )
5. So, 5C2 is: ( 5! * inv[6] * inv[2] ) % M = ( 120 * 166666668 * 500000004 ) % M = 10

*/

ll calculateNcR(ll n, ll r)
{
    return (factorial[n] * ((modular_inverse(factorial[r]) * modular_inverse(factorial[n - r])) % M)) % M;
}

int main()
{
    // pre-populating factorial array up to 10^6 (% M)
    factorial[0] = 1;
    factorial[1] = 1;

    for (int i = 2; i < N; i++)
    {
        factorial[i] = factorial[i-1] * i % M;
    }

    ll n, m;
    cin >> n >> m;

    ll totalPathsFromStartToTrap[m];

    ll y, x;
    for (int i = 0; i < m; i++)
    {
        cin >> y >> x;

        //maintaining trap positions in a vector
        trapIndex.push_back({y, x});
    }

    // sorting the grid, so that we calculate the paths for earlier trap's first
    sort(trapIndex.begin(), trapIndex.end(), compareTrap);

    ll totalPaths = calculateNcR((n-1) * 2, n - 1); // counting all possible pat

    for (int i = 0; i < m; i++)
    {
        y = trapIndex[i].y;
        x = trapIndex[i].x;

        ll maxOfXY = max(y,x); // either right or down
        ll minOfXY = min(y,x); // either right or down

        ll maxMove = maxOfXY + minOfXY - 2; // subtracting the starting and trap block from the count
        ll minMove = minOfXY - 1; // subtracting the trap block from the count

        totalPathsFromStartToTrap[i] = calculateNcR(maxMove, minMove);

        for (int j=0; j<i; j++)
        {
            ll tempY, tempX;
            tempY = trapIndex[j].y;
            tempX = trapIndex[j].x;

            if (tempY > y || tempX > x)
            {
                continue;
            }
            else //overlap, so, we need to remove the double counted paths!
            {
                // considering a trap as child when it falls within the range(x,y) of a bigger/mother trap
                // maximum move (right/down) form child trap to mother trap
                ll childToMotherMaxMove = max(y - tempY, x - tempX);

                // minimum move (right/down) form child trap to mother trap
                ll childToMotherMinMove = min(y - tempY, x - tempX);

                // counting all possible way from child trap to mother trap
                // total count of moves = childToMotherMaxMove + childToMotherMinMove (right + down)
                ll totalPathsFromChildToMother = calculateNcR(childToMotherMaxMove + childToMotherMinMove, childToMotherMinMove);

                // updating path count by subtracting illegal path's generated by child trap
                totalPathsFromStartToTrap[i] = (totalPathsFromStartToTrap[i] - totalPathsFromStartToTrap[j] * totalPathsFromChildToMother % M) % M;
            }
        }

        // maximum move (right/down) form trap to destination
        ll trapToDestMaxMove = n - minOfXY;

        // minimum move (right/down) form trap to destination
        ll trapToDestMinMove = n - maxOfXY;

        // counting all possible way from trap to bottom right
        // total count of moves = trapToDestMaxMove + trapToDestMinMove (right + down)
        ll totalPathsFromTrapToDest = calculateNcR(trapToDestMaxMove + trapToDestMinMove, trapToDestMinMove);

        // subtracting illegal path's generated by a trap
        totalPaths = (totalPaths - totalPathsFromStartToTrap[i] * totalPathsFromTrapToDest % M) % M;

        if (totalPaths < 0)
        {
            totalPaths += M;
        }
    }
    cout<<totalPaths<<endl;
}

/* Sample Test Cases:

4 2
3 1
3 3

Output: 6

6 1
3 3

Output: 132

5 2
4 2
3 4

Output: 24

5 3
4 2
3 4
5 4

Output: 1

6 3
4 2
3 4
6 3

Output: 83
*/