```
class Solution(object):
def findPaths(self, m, n, N, i, j):
# m x n board, can move max N times, start pos i, j
numWays = 0
# next state just keeps track of what possible coordinates we can go from a given coordinate
nextStateDict = self.createNextStateDict(m, n)
# keeps track of how many times we see a coordinate
# at start, we only see one coordinate, which are the start coordinates
posCount = {(i,j):1}
for _ in xrange(N):
new_pos_count = dict()
# iterate through all the positions
for pos in posCount:
# get all valid new positions from pos
validMoves = nextStateDict[pos]
numWays += (4 - len(validMoves)) * posCount[pos]
for newPos in validMoves:
if newPos not in new_pos_count:
new_pos_count[newPos] = 0
new_pos_count[newPos] += posCount[pos]
posCount = new_pos_count
return numWays % (10**9 + 7)
def getValidMoves(self, m, n, i, j):
# given pos (i,j), what next states can i be in?
posAfterOneMove = [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]
return [(a,b) for a,b in posAfterOneMove if (0 <= a < m) and (0 <= b < n)]
def createNextStateDict(self, m, n):
# for each pos in board, get a dict of next possible states
d = dict()
for row in range(0, m):
for col in range(0, n):
d[(row,col)] = self.getValidMoves(m, n, row, col)
return d
```