\(i\) 回目の移動後に \(j\) 階にいる方法の数を \(D(i, j)\) とすると, 最後にエレベータ \(k\) に乗ったとすると

\[D_k(i, j) = \sum_{l=L_k}^{R_k} D(i-1, l) \ (L_k \leq R_k)\]

となり,

\[D(i, j) = \sum_{k=1}^M D_k\]

となる. 前者の式は累積和を計算し, 後者の式は imos 法を使えばいい.