\(dp[h][r] = \)(\(h\) 階に降りてきたときの部屋が部屋 \(r\) である方法の数) という DP を考えます．初期値は \(dp[H][1] = 1\) で，答えは \(dp[0][1]\) に現れます．（「\(1\) 階の部屋 \(1\) で行動を終える」を，便宜上「\(0\) 階の部屋 \(1\) に降りてくる」と考えればよいです）

この DP の遷移は，\(dp[h - 1][s] \leftarrow \sum_{1 \leq r \leq R} dp[h][r] \times c(r, s)\) となります．ただし，\(c(r, s)\) は，「同一フロアの部屋 \(r\) から部屋 \(s\) まで同じ部屋を \(2\) 回以上通らずに到達する方法の数」です．

まずは，\(c(r, s)\) を求める方法を考えます．これは，始点 \(r\) のすべてに対して \(dp_2[S][j] = \)(これまで訪れた頂点の集合が \(S\) であり，現在の頂点が \(j\) である方法の数) という DP を遷移させていくことによって，\(O(2^R R^3)\) 時間で求められます．

\(c(r, s)\) が求められたので，元の DP を遷移させていくことで答えを求めます．定義式に従って愚直に求めることは \(H\) が大きいため不可能ですが，遷移が \(h\) によらないことを利用し，行列累乗で高速化できます．これにより，元の DP の遷移も \(O(R^3 \log H)\) 時間で行えます．

以上を実装することによりこの問題が解けます．計算量は \(O(R^3 (2^R + \log H))\) です．