\(M=\max (H_i) \ (= 10)\) とします。 愚直にクエリ毎に DP をするとクエリ毎に \(O(NM)\) かかるように見えますが、実は \(O(N)\) でできます（＊）。 よって全体で \(O(ND)\) （\(ND \leq 1.5 \times 10^9\)）ですが、制限時間が \(8\) 秒と長いので重い実装でなければ間に合います。

（＊）\(s\) からはじめて各マスごとに、その位置に到達する方法の数 \(a\) を管理します。 \(h_i\) が十分大きければ \(a\) はマス毎に \(2\) 倍になりますが、実際は \(h_i\) が切れるタイミングで減ります。どのマスでどれだけ減るかをメモすることでマスごとに \(O(1)\) で更新できます。

ACコード（PyPy3）