\(A_i\) の中で最小を取る \(i\) (そのようなものが複数ある場合は最小の \(i\)) をとり，\(m\) と置きます．

\(m\) を固定したとします． この時あり得る \(A_i\) は，以下の手順で得られる数列に限られます．

• 定数 \(C\) を選び，\(A=(C,C,\cdots,C)\) と初期化し，以下の \(2\) つの操作を繰り返す．
• \(i < m\) を選び，\(A_i,A_{i-1},\cdots,A_1\) に，\(1,2,3,\cdots\) を足し込む．（この操作を \(i=m-1\) として少なくとも \(1\) 回は実行する必要がある）
• \(i > m\) を選び，\(A_i,A_{i+1},\cdots,A_N\) に，\(1,2,3,\cdots\) を足し込む．

すると結局問題は，重み \(N,1,3,6,\cdots\) のアイテムがあり，それらを組み合わせて \(M\) にする方法は何通りか，となります． アイテムの種類数は \(O(\sqrt{M})\) 通りだけ考えればよいので，これは \(O(M\sqrt{M})\) で解けます．

\(m\) が固定されていない場合を考えます．\(m=1,2,\cdots\) と変化させることにします．\(m\) を変化させるたびに，上述の DP を計算することができます．毎回一からすべて計算していては間に合いませんが，持っているアイテムの差分に注目すると，DP を \(O(M)\) で計算し直すことができます．

\(m\)は最初の \(O(\sqrt{M})\) 通りだけ考えれば良いので，全体で \(O(M\sqrt{M})\) で計算できます．