You can store the coordinates of the obstacles in a set so that we can check if it is possible to teleport to a point in an \(O(\log M)\) time.

First, consider the following easier problem:

• You may perform two kinds of teleportations, \((x+1,y)\) and \((x,y+1)\); the other conditions are the same.

This problem can be solved with a DP (Dynamic Programming) where \({\rm dp}[n][x][y]=\) the number of paths that end up in \((x,y)\) after \(n\) teleportations
in a total of \(O(N^3 \log M)\) time.

Let’s get back to the original problem. This case, the possible values of \((x,y)\) is relatively small, so we can solve it in a total of \(O(N^3(\log N+\log M))\) time by storing the DP table in a dictionary. If you use a fast language, your code will be accepted.

Sample code (C++)

Instead of coordinates, we can perform the following DP where we maintain how many times we used each move to solve it in a total of \(O(N^3\log M)\) time:

\({\rm dp}[n][x][y]=\) the number of paths in which you make each of the moves \(x\), \(y\), and \(z\) times, during the \(n\) teleportations

If you maintain the array naively, it costs \(O(N^4)\) spacial cost, but since \(n=x+y+z\), we don’t need to store \(z\) as the state, so it costs \(O(N^3)\).

In the sample code below, we store only \({\rm dp}[n-1]\) and \({\rm dp}[n]\) to reduce the spacial complexity to \(O(N^2)\).
Sample code (C++)
Sample code (Python)