Grid Paths II

n,m = map(int, input().split())
if(n==1):
    print(1)
d = {}
for i in range(m):
    t = input()
    d[t]=1
g=[[0] for x in range(n)]
for i in range(1,n):
    if("{} {}".format(i+1, 1) not in d):
        g[i][0]=1
    else:    
        g[i][0]= -1
        break
l=1
for i in range(1, n):
    if ("{} {}".format(1, i+1) not in d):
        g[0].append(l)
    else:
        g[0].append(-1)
        l=0
for y in range(1,n):
    for x in range(1,n):
        if ("{} {}".format(y+1, x+1) in d):
            g[y].append(-1)
            continue
        g[y].append(0)
        if g[y-1][x]>-1:
            g[y][x]+=g[y-1][x]
        if g[y][x-1]>-1:
            g[y][x]+=g[y][x-1]
print(g[n-1][n-1]%(10**9 + 7))
 
 
 
 
 
 
 
 
 
 
 
 
 
 
# n,m = map(int, input().split())
# if(n==1):
#     print(1)
# d={}
# for i in range(m):
#     y=input()
#     d[y] = True
# def r(y,x):
#     if(y==n and x==n):
#         return 1
#     if("{} {}".format(y-1,x-1) in d):
#         return 0
#     return r(y+1, x) + r(y, x+1)
# print(r(0, 0))
        

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