https://emtubasa.hateblo.jp/entry/2019/01/01/172151

解法

bitDPです。だんだん詰め合わせ感が増えてきました。
$m[i][j] =$ 同じ階層で $i$ から $j$ に移動するパターン数
とすると、これを $R\times R$ の行列に見立てて $H$ 乗すると、 $m[1][1]$ が答えになります。
$m[i][j]$ を求めることさえできれば、あとはこの行列式の $2^{k}$ を求めていき、 $O(R^{2}logH)$ 程度で答えが求まります。
ということで、この行列式を完成させることを考えます。
$dp[i][j][S] = i$ から $S$ の部屋を通り、 $j$ にいくパターン数
とします。部屋が $16$ までしかないので、通る部屋の状態 $S$ をビット列で持つことができます(自分は、スタート地点とゴール地点の $i,j$ 両方のビットも立てました)。
このとき、 $m[i][j]$ は、 $dp[i][j][S]$ の全ての状態 $S$ に対する総和になります。
このDPは、スタート地点 $i$ から幅優先探索をすることで求めることができます。
今、 $S$ の部屋を通り、 $j$ の部屋にいるとします。すると、 $S$ に含まれていないかつ、 $j$ からいくことのできる部屋 $k$ については、部屋 $k$ が $2^{k}$ で表されることを利用して、
$dp[i][k][S+2^{k}] += dp[i][j][S]$
という遷移を行えばよいです。
ということで、すべての部屋をスタート地点に選んだ幅優先探索を行い、このDPを埋めることで、 $m[i][j]$ を完成させることができます。
あとは、 $H$ 乗すれば、答えが求まります。