Language: C++

/*

  This is an optimization for based question where the complexity is n*n but here 
  it will be o(obstacles * obstacles) where obstacles are less than grid dimension n.

  User:- sanyam
*/

#include<bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define ll long long int
#define mod 1000000007
#define w(t) int t;	cin>>t while(t--)
#define triplet pair<int,pair<int,int>>
#define vi vector<int>
#define vll vector<ll>
#define pi pair<int,int>
#define pll pair<ll,ll>
#define fastIO ios_base::sync_with_stdio(0);	cin.tie(0);	cout.tie(0);
#define loop(i, k, n) for(ll i=k; i<n; i+=1)
#define loop2(i, k, n) for(ll i=k; i>=n; i--)
#define init_arr(i,val) memset(i, val, sizeof(val))
#define sort_cut(x) (x).begin(), (x).end()

const ll inf = 1e18;

void take_fileIO(){
  #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
  #endif
  return;
}


/* ---------------------Code--------------------  */
ll dp[3001];
ll fact[200001];
ll invofFact[200001];

ll power(ll x, ll exp){
  if(exp==0)
    return 1;
  if(exp==1)
    return x%mod;
  ll res = power(x, exp/2)%mod;
  if(exp & 1){
    return (res%mod * res%mod * x%mod)%mod;
  }
  return (res%mod * res%mod)%mod;
}

ll inverse(ll num){
  return power(num , mod-2)%mod;
}

ll NCR(ll n, ll r){
  return (fact[n]%mod * invofFact[r]%mod * invofFact[n-r]%mod)%mod;
}

ll calc_ways(ll i, ll j, ll ei, ll ej){
  ll down = ei-i;
  ll right = ej-j;
  if(down<0 || right<0) return 0;
  
  else return NCR(down+right, right)%mod;
}

bool comp(pi &a, pi &b){
  ll dist1 = (a.first-1)*(a.first-1) + (a.second-1)*(a.second-1);
  ll dist2 = (b.first-1)*(b.first-1) + (b.second-1)*(b.second-1);
  return dist1 <= dist2;
}

void solve_dp_for_obstacles(vector<pi> &obstacles, ll n, ll h, ll w) {
  dp[0] = calc_ways(1, 1, obstacles[0].first, obstacles[0].second)%mod;
  for(int i=1; i<n; i++){
    dp[i] = calc_ways(1, 1, obstacles[i].first, obstacles[i].second)%mod;
    
    for(int j=0; j<i; j++){
      // ll distj = dist(obst
      dp[i] = (mod + dp[i]%mod - calc_ways(obstacles[j].first, obstacles[j].second, 
                          obstacles[i].first, obstacles[i].second)%mod)%mod;

    }
  }
  return;
}

void preprocess(){
  fact[0]=1;
  invofFact[0]=1;
  for(ll i=1; i<=200000; i++){
    fact[i] = (fact[i-1]%mod * i%mod)%mod;
    invofFact[i] = inverse(fact[i])%mod;  
  }
  return;
}

void solve(){
  ll h,w,n;
  cin>>h>>w>>n;
  
  vector<pair<int,int>>obstacles;
  loop(i, 0, n){
    ll x, y;  cin>>x>>y;
    obstacles.push_back(mp(x, y));
  }
  
  init_arr(ncr, 0);
  init_arr(dp, 0);
  init_arr(invofFact, -1);

  sort(obstacles.begin(), obstacles.end(), comp);
  preprocess();

  solve_dp_for_obstacles(obstacles, n, h, w);

  ll ans = calc_ways(1, 1, h, w)%mod;
  // cout<<ans<<endl;

  for(int i=0; i<n; i++) {
    ans = (mod + ans%mod - (dp[i]%mod*calc_ways(obstacles[i].first, obstacles[i].second, h, w)%mod)%mod )%mod;
  }
  // if(ans<0) ans=0;
  cout<<ans<<endl;
  return; 
}

int main(){

  fastIO;
  //take_fileIO();
  solve();
  return 0;
}

Compiler output:
a.cc: In function 'void solve()':
a.cc:113:12: error: 'ncr' was not declared in this scope
  113 |   init_arr(ncr, 0);
      |            ^~~
a.cc:25:32: note: in definition of macro 'init_arr'
   25 | #define init_arr(i,val) memset(i, val, sizeof(val))
      |                                ^