Following @StefanPochmann 's excellent suggestion, let `inside(t)`

be the number of paths that remain inside the board after `t`

moves. Then the number of paths that exit the boundary on the `t+1`

'th move is `4*inside(t) - inside(t+1)`

.

Suppose we are to make `t`

moves. We'll make `k`

horizontal moves and `t-k`

vertical moves. We can shuffle the order of these moves in `binom(t, k)`

ways (the binomial coefficient.) So in total:

`inside(t) = sum_{k=0..t} (number of ways to stay on the board in k moves horizontally) * (number of ways to stay on the board in t-k moves vertically) * binom(t, k)`

.

We can find in advance our answers to the 1D problem by a simple dp. There probably exists an even faster approach for this, but I can't think of one right now.

```
def findPaths(self, R, C, N, sr, sc):
MOD = 10**9 + 7
def binom_all(n):
ans = [1]
r = 1
for i in xrange(1, n+1):
r *= n - i + 1
r /= i
ans.append(r)
return ans
def solve_1D(A):
ans = [1]
for time in xrange(N+1):
Anew = [0] * len(A)
inside = 0
for i, u in enumerate(A):
if i >= 1:
Anew[i-1] += u
inside += u
if i < len(A) - 1:
Anew[i+1] += u
inside += u
A = Anew
ans.append(inside)
return ans
dprow = solve_1D([+(r == sr) for r in xrange(R)])
dpcol = solve_1D([+(c == sc) for c in xrange(C)])
binoms = [binom_all(n) for n in xrange(N+1)]
def inside(t):
ans = 0
for k in xrange(t+1):
ans += dprow[k] * dpcol[t-k] * binoms[t][k]
return ans % MOD
S = sum(inside(t) for t in xrange(N))
return (3*S - inside(N) + inside(0))%MOD
```