マス \(x\) に到達可能なとき \(f_x=1\)，そうでないとき \(f_x=0\) とします．また \(v_x=(f_x,f_{x-1},\dots,f_{x-B+1})^{T}\) とします． \(v_1=(1,0,\dots,0)^{T}\) です．

\(B\times B\) 行列 \(P,Q\) を以下のように定めます．

• \(A\leq i\leq B\) に対し \(P_{1,i}=1\)．
• \(2\leq i\leq B\) に対し \(P_{i,i-1}=Q_{i,i-1}=1\)．
• 以上において現れない成分は全て \(0\)．

行列積を (or, and) で計算することにすれば，\(x\) が悪いマスでないならば \(v_x=Pv_{x-1}\)，悪いマスならば \(v_x=Qv_{x-1}\) です．

従って \(v_N\) は \(v_1\) に左から \(P,Q\) の冪を \(O(M)\) 個掛けたものになっています．

bit 演算を用い，\(P,Q\) の(二冪)乗を前計算すれば計算量は \(O(B^2\log N+MB\log N)\) などになります．

実装例(C++, 13ms)