def helper(x,y,hb,z,w,debug=False):
    ans1=ans2=ans3=ans4=0
    if x+1<len(hb) and hb[x+1][y]>hb[x][y]:
        if debug:print(x+1,y)
        if x+1==z and y==w:return 1
        ans1 = helper(x+1,y,hb,z,w,debug)
    if x-1>=0 and hb[x-1][y]>hb[x][y]:
        if debug:print(x-1,y)
        if x-1==z and y==w:return 1
        ans2 = helper(x-1,y,hb,z,w,debug)
    if y+1<len(hb[0]) and hb[x][y+1]>hb[x][y]:
        if debug:print(x,y+1)
        if x==z and y+1==w:return 1
        ans3 = helper(x,y+1,hb,z,w,debug)
    if y-1>=0 and hb[x][y-1]>hb[x][y]:
        if debug:print(x,y-1)
        if x==z and y-1==w:return 1
        ans4 = helper(x,y-1,hb,z,w,debug)
    return ans1+ans2+ans3+ans4

def solution():
    N,M = 6,5
    hb = [[0,1,0,0,0],[0,2,3,0,0],[0,0,4,5,6],[0,0,19,8,7],[0,0,20,9,0],[0,0,0,10,0]]
    x,y,z,w = 0,1,5,3
#     N,M = 5,5
#     hb = [[0,1,0,0,0],[0,2,3,0,0],[0,0,4,5,6],[0,0,9,8,7],[0,0,10,0,0]]
#     x,y,z,w = 0,1,4,2
    
    flag = [[0 for i in range(len(hb[0]))] for j in range(len(hb))]
    flag[x][y]=1
    output = helper(x,y,hb,z,w,debug=False)
    print(output%1000000000)

solution()