この解法ではdp[i][j] = (マスjからi回以内の移動でゴールできる確率)とします。
(今回の実装例では回数に関する変数を使わずに記述しています。)
遷移の式をみるとdp[i]の各要素はdp[i - 1]内の一定幅の部分和として表すことができるので、畳み込みによって遷移を計算できることがわかります。

Pythonライブラリのnumpyを用いれば、1回の遷移が1回の関数呼び出しのみで書けるので実装が楽です。 実装例

畳み込みの部分に数論変換などを使えば\(O\left(K(N + M)\log(N + M)\right)\)で解くことも可能ですが、この問題の制約でその必要はないでしょう。