Grid Paths II

import sys


def g(xi, yi, n, traps, m):
    m[(n, n)] = 1
    q = []
    r = 2*(n)
    for i in range(r, 1, -1):
        for x in range(i-1, 0, -1):
            if 1>x or x > n:
                continue
            y = i - x
            if 1>y or y > n:
                continue
            
            if traps.get((x, y)) is not None:
                m[(x, y)] = 0
                continue

            if x == n and y == n:
                continue
            
            
            a=0
            b=0
            if x < n :
                u = (x+1,y)
                if m.get(u) is not None:
                    a = m[u]
                else:
                    a = g(x+1,y,n,traps,m)
            if y < n :
                u = (x,y+1)
                if m.get(u) is not None:
                    b = m[u]
                else:
                    b = g(x,y+1,n,traps,m)
            c = a+b
            m[(x, y)] = c

    return m[(1,1)]

    

def main():
    s = input()

    (n, traplen)= s.split()
    n = int(n)
    traplen = int(traplen)
    traps = {}
    for i in range(traplen):
        s = input()
        (t1, t2)= s.split()
        traps[(int(t1), int(t2))] = 1
    m = {}
    result = g(1, 1, n, traps, m)

    print(result % (10**9 + 7))


if __name__ == "__main__":
    main()

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