Grid Paths II

#include <bits/stdc++.h>
#define ll long long int 
using namespace std;

set<pair<int, int>> traps; 
vector<int> dp {};
ll M = 1e9+7;
int main () {
    int n, m;
    cin >> n >> m;

    dp = vector<int> (n+1);
    for (int i=0; i<m; i++) {
        int a, b;
        cin >> b >> a;
        if ((a==n && b==n) || (a==1 && b==1))  {
            cout << 0;
            return 0;
        }
        traps.insert(make_pair(a, b));
    }
    
    dp[1] = 1;
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {
            if (traps.find({i,j}) == traps.end()) {
                dp[j] = (dp[j-1]%M+ dp[j]%M) %M;
            } else dp[j] = 0;
        }
    }


    cout << dp[n];
    // cout << "\n";
    // for (auto i:dp) {
    //     cout << i << " ";
    // }
    // cout << endl;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: TIME LIMIT EXCEEDED

Test 8

Verdict: TIME LIMIT EXCEEDED

Test 9

Verdict: TIME LIMIT EXCEEDED

Test 10

Verdict: TIME LIMIT EXCEEDED