Use BFS to track next possible moves: The idea is for each (x,y), store how many ways to get here.

if (x,y) is a corner, total number increases by count * corner

if (x,y) is a boundary, total number increase by count * boundary

if (x,y) is interior, total number will not increase

```
int findPaths(int m, int n, int N, int i, int j) {
if (N == 0)
return 0;
long long total = 0;
int M = 1000000007;
queue<pair<int, int> > q;
q.push({ i * n + j, 1 });
int incr[5] = { 1, 0, -1, 0, 1 };
int corner = (m == 1 || n == 1) ? 3 : 2;
if (m == 1 && n == 1)
corner = 4;
int boundary = (m == 1 || n == 1) ? 2 : 1;
//for each (x,y) stores how many ways to get here.
while (!q.empty())
{
int num = q.size();
unordered_map<int, long long> nexts;
for (int k = 0; k < num; ++k)
{
int x = q.front().first / n;
int y = q.front().first % n;
long long count = q.front().second;
//if (x,y) is a corner, total number increase by count * corner
//if (x,y) is a boundary, total number increase by count * boundary
//if (x,y) is interior, totoal number will not increase
if (x == 0 && y == 0 || x == m - 1 && y == 0 || x == 0 && y == n - 1 || x == m - 1 && y == n - 1)
total += (long long)corner * count;
else if (x == 0 || y == 0 || x == m - 1 || y == n - 1)
total += (long long)boundary *count;
total = total % M;
q.pop();
//accumulate number of ways at same next_x, next_y
for (int i = 0; i < 4; ++i)
{
int next_x = x + incr[i];
int next_y = y + incr[i + 1];
if (next_x >= m || next_x < 0 || next_y >= n || next_y < 0)
continue;
nexts[next_x*n + next_y] += count;
}
}
--N;
if (N == 0)
break;
for (auto next : nexts)
q.push({ next.first, next.second % M });
}
return total%M;
}
```